https://www.acmicpc.net/problem/13325

 

13325번: 이진 트리

입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가

www.acmicpc.net

루트에서 모든 리프노드 까지의 거리가 모두 같게만든 후 모든 가중치의 합의 최소를 구하는 문제입니다.

 

입력으로 주어지는 트리는 무조건 포화 이진 트리(perfect binary tree)이고,

이 문제는 독특하게 노드가 아닌 간선만 입력으로 주어집니다.

 

높이가 1이면 2개의 가중치, 2면 4개의 가중치이므로 높이 N에는 2^N개의 가중치가 있다는 것을 알 수 있습니다.

따라서 입력으로 2가 주어지면 높이가 1인 가중치(2) + 2인 가중치(4) = 총 6개를 입력으로 받습니다.

 

이 문제는 리프에서부터 같은 부모로 이어지는 간선 두개를 비교하여 합을 같게 맞추는 식으로 루트까지 올라가면서 계산하는 방식으로 해결할 수 있습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[1 << 21];
int N, ans;
 
void func() {
    for (int i = N; i > 0; i--) {
        for (int j = (1 << i); j < (1 << (i + 1)); j += 2) {
            ans += abs(list[j] - list[j + 1]);
 
            list[j / 2+= max(list[j], list[j + 1]);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 2; i < (1 << N + 1); i++) {
        cin >> list[i];
        ans += list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs
 
 
 

'algorithm > dp' 카테고리의 다른 글

boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19
boj 1563 개근상  (0) 2021.06.02
boj 10800 컬러볼  (0) 2021.04.09
boj 12869 뮤탈리스크  (0) 2021.04.04

+ Recent posts