13325. 이진 트리

오랜만이다 그죠?

13325번: 이진 트리

---

문제의 조건은 다음과 같다.

1. 어떤 에지들의 가중치를 증가시켜서
2. 루트에서 모든 리프까지의 거리가 같게 하면서
3. 에지 가중치들의 총합이 최소가 되도록 하자.

어떻게 증가시킬 것인가

2번 조건을 보면, 루트에서 모든 리프까지의 거리가 같아야 한다. 동시에 3번 조건에 의해 루트에서 각 리프까지의 거리는 최대한 작은 값이어야 한다. 이 값을 ``target``이라고 정의하자. ``target``을 어떻게 구해야 할까?

 

조건을 종합하면 ``target``은 주어진 트리에 대해 루트에서 리프까지의 거리 중 최댓값이 되어야 한다. 그래야만 위의 세 가지 조건을 모두 만족할 수 있다. 

• 가중치를 감소시킬 수는 없으므로, ``target``은 최소한 ``max_dist = max(리프까지의 거리)``보다는 커야 한다.
• 모든 리프까지의 거리를 ``target``으로 통일한다.
• 가중치들의 총합이 최소여야 하므로, 증가시키는 값도 최소여야 한다. 따라서 ``target``은 ``max_dist``여야 한다.

``target``이 ``max_dist``보다 크다면 ``target``보다 작으면서 위의 조건을 모두 만족하는 값이 적어도 하나 존재한다. 예를 들어 ``target-1``이 조건을 만족하므로 ``target``은 정답이 될 수 없다.

어떻게 구할 것인가

트리의 특성상 재귀를 활용하면 편리한 경우가 많다. 이 문제 역시 마찬가지다. ``i``번 노드를 루트로 하는 서브 트리에서 ``target``을 구하는 함수를 ``search(i)``으로 정의하면, ``target = max(left_w + search(left), right_w + search(right))``으로 구할 수 있다. 여기서 ``left_w``와 ``right_w``는 각각 ``i``번 노드의 왼쪽, 오른쪽 간선의 가중치를 의미한다.

 

식의 의미를 이해할 수 있을 것이다. 간단히 요약하면 왼쪽 서브 트리의 ``max_dist``와 오른쪽 서브 트리의 ``max_dist``를 비교하여 더 큰 값을 ``target``으로 취한다.

이제 실제로 증가시키자

이 부분은 메모리가 부족하여 적지 않는다.

 

농담이고 ㅋㅋ 직접 해보길 바란다. 어렵다면 내 코드를 참고해도 좋다.

---