[백준] No.1693 - 트리 색칠하기 (C++)

문제

 

https://www.acmicpc.net/problem/1693

1693번: 트리 색칠하기

 

 

풀이

 

solved.ac 난이도: Platium 3

 

상당히 해결하기 어려웠던 트리에서의 다이나믹 프로그래밍 문제.

해당 문제의 풀이는 koosaga님과 BaaaaaaaarkingDog님의 풀이를 참고하였습니다.

 

T(N): 반드시 N개의 색을 사용해야 트리를 최소 비용으로 칠할 수 있는 트리들 중에서 최소 노드 개수 라고하자.

 

반드시 N개의 색을 써야 한다면 루트 노드의 자식 노드들이 모두 1~N-1의 색으로 칠해져 있어 어쩔 수 없이 루트를 N으로 칠하는 경우이다. 

 

이러한 경우, 자식 노드들의 서브 트리도 루트를 해당 수(i)로 칠해야만 하는 트리를 구성하기 때문에

최소 노드 개수 T(N)은 아래와 같이 재귀적으로 표현할 수 있다.

 

T(1) = 1

T(2) = T(1) + 1 = 2

T(3) = T(2) + T(1) + 1 =  ( T(1) + 1 ) + 2 = 4

T(4) = T(3) + T(2) + T(1) + 1 = ( T(2) + T(1) + 1 ) + ( T(1) + 1 ) +  T(1) + 1 = 4 + 2 + 1 + 1 = 8

...

T(N) = T(N-1) + T(N-2) + ... + T(2) + T(1) + 1

= 2^(N-2) + 2^(N-3) + ... + 2^(1) + 2^0 =

2^(N-1)

이때 뒤에 붙는 + 1은 자기 자신(루트 노드)을 N번 색으로 칠하는 것을 의미한다.

 

T(N)의 의미를 조금 더 자세히 생각해보자.

위의 식에 따르면 T(3) =  4이다. 이때의 트리는 아래와 같다.

 

3개의 색으로 칠할 수 있는 최소 노드의 개수는 4개임을 의미한다.

 

물론 4개의 노드는 아래와 같이 더 작은 비용으로 칠할 수도 있다.

즉, T(N)은 최소의 비용만을 선택함에도 N의 색을 모두 사용해야 하는 최악의 경우이다.

 

여기서 우리가 T(N) (반드시 N개의 색을 사용해야 트리를 최소 비용으로 칠할 수 있는 트리들 중에서 최소 노드 개수)

을 찾는 이유는 노드의 수가 최대 100,000의 값을 가지기 때문이다.

만약 이를 그대로 dp로 구현한다면 100,000(각각의 노드를) X 100,000(1번 색에서 ~ 모든 색으로 모두 칠해보는 경우) = 10,000,000,000의 터무니없이 큰 경우의 수에서 최소 비용을 찾아보아야 한다.

하지만 T(N)을 알고 있다면 100,000개의 노드를 가능한 최소 비용의 색만을 선택할 때 적어도 몇 개의 색이 필요한지 알 수 있다.

 

T(N) = 2^(N-1) 이기 때문에 T(18) = 2^(17) = 131,072이다.

따라서 100,000개의 노드는 18개의 색으로도 모든 경우의 최소 비용 트리 구해낼 수 있다.

 

이후에는 DFS형식으로 최소 비용을 구하는 코드를 작성해 주면 된다.

 

코드