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 |