[백준 / BOJ] 13325 이진트리

문제

출처 : www.acmicpc.net/problem/13325

13325번: 이진 트리

1~K높이의 이진트리가 주어졌을때, 한 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 각 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 모두 같게하면서 에지의 가중치합을 최소로 만드는 문제다.

 

풀이

(백준에서 1초에 반복문이 1억번 돈다고 들은것같다..)

최악의 경우인 1^1 + 1^2 + 1 ^ 3 + ... + 2^20 을 대충 300만으로 잡았을때,

트리를 만드는데 300만번

가중치 업데이트 300만번

업데이트 된 가중치 탐색 300만번

많아야 900만번으로 1초안에 수행이 가능하다.

 

트리를 만들고 바텀업 방식으로 구현했다.

아래에서 부터 자신의 "리프노드가 갖고있는 가중치의 합" 들을 비교해주며 올라간다.

 

 

(빨강색 네모칸하나에 포함된 노드를 각각의 트리라고 생각하자)

이때, 노드 2를 루트로 하는 트리가 갖고있는 한방향의 가중치의 합은,

 

- max(4 번 노드가 갖고있는 가중치의 합 , 5번 노드가 갖고있는 가중치의 합)

- 4번노드는 2의 가중치를 갖고있고, 5번 노드는 1의 가중치를 갖고있다.

- 따라서 2번노드가 갖고있는 한방향의 가중치는 2이다.

- 5번노드가 4번노드보다 더 작으니 5번노드를 업데이트 시켜준다.

- 2번노드가 갖고있는값 + 1번노드에서 2번노드로 가는 가중치를 리턴한다.

 

위 과정을 반복하면 루트노드에서부터 리프노드까지 모든 가중치의 값이 업데이트 된다.

이후 반복문을 돌려 가중치값을 전부 더해주면 답이나온다.

 

소스코드

https://github.com/devxb/JJUNalgo/tree/master/13325%20%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC

devxb/JJUNalgo