티스토리 뷰

알고리즘 관련/BOJ

BOJ)13325 이진 트리

JASON 자손9319 2017. 1. 18. 21:36
문제: icpc.me/13325


포화 이진트리의 높이 K가 주어 질 때 에지의 가중치를 증가시켜서 루트에서부터 리프까지의 거리를 모두 같게 만드는 문제이다.


아래에서 부터 부모가 같은 두노드의 엣지의 가중치 차이를 바텀업으로 중첩시켜서 증가시켜주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[<< 22], r;
int main() {
    scanf("%d"&n);
    for (int i = 2; i < (<< (n + 1)); i++) {
        scanf("%d"&a[i]);
        r += a[i];
    }
    for (int i = n; i > 0; i--) {
        for (int j = (<< i); j < (<< (i + 1)); j += 2) {
            r += abs(a[j] - a[j + 1]);
            a[j / 2+= max(a[j], a[j + 1]);
        }
    }
    printf("%d", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)4386 Freckles  (0) 2017.01.19
BOJ)4343 Arctic Network  (0) 2017.01.19
BOJ)13325 이진 트리  (1) 2017.01.18
BOJ)11975 Build Gates  (0) 2017.01.18
BOJ)11974 Subsequences Summing to Sevens  (0) 2017.01.18
BOJ)11973 Angry Cows  (0) 2017.01.18
TAG
댓글
댓글쓰기 폼