Monday, January 27, 2014

acmicpc.net 1763 - 트리색칠

Problem Link

N개의 노드를 가지고 있으며, 루트가 있는 트리의 각 노드에 가중치가 부여돼 있다. 임의의 노드의 번호를 i라 하고, i번 노드에 부여된 가중치를 C[i]라 한다. 한 노드를 색칠하는 데에는 비용이 드는데, i번 노드가 F[i]번째로 색칠되는 노드라면, i번 노드를 색칠하는 데 드는 비용은 C[i]*F[i]로 계산된다. 전체 트리를 색칠하는 데 드는 비용은 각 노드를 색칠하는 데 드는 비용의 합이다. 단, 어떤 노드를 색칠하기 위해서는 그 노드의 부모 노드가 이미 색칠되어 있어야 한다. 따라서 루트가 가장 먼저 색칠되어야 한다. 이러한 규칙에 따를 때, 최소의 비용으로 트리를 색칠해야한다.
  문제를 풀기 위해서는 다음 2가지의 정리가 쓰인다.
1. Root가 아닌 노드 p가 가중치가 가장 크다면, p의 부모 노드 q가 선택된 이후에는 p를 선택하는 것이 최적이다. (귀류법을 통해 쉽게 증명 가능)
2. '1.'에 의해 q와 p는 인접하며 q가 선택된 이후에만 p가 선택될 수 있다. 이 때, p와 q를 하나의 노드 r로 생각할 수 있는데 r의 자식노드 k는 p와 q의 자식노드이다. 노드 r의 가중치는 (C[p]+C[q])/2가 된다. 트리의 형태가 총 N개의 노드에서 N-1개의 노드로 줄어든 것이다. 이것을 확장시켜 m개의 노드들을 하나의 노드로 생각한다면 그때의 가중치는 (C[x(1)]+C[x(2)]+...+C[x(m)])/m이 된다. 증명은 수학적 귀납법을 통해 가능하다.

Source Code

No comments:

Post a Comment