본문 바로가기

알고리즘 관련/BOJ

BOJ)13325 이진 트리

문제: 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)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