이동식 저장소

오랜만이다 그죠?

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

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으로 취한다.

이제 실제로 증가시키자

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

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