백준 - 트리 색칠하기(1693)

문제

이 문제는 BarkingDog 님의 블로그를 참고했습니다.

 

N개의 정점을 가진 트리에 대해 색깔의 개수가 bound되어 있다고 가정하고 계산해 봅시다.

 

먼저 다음과 같이 수열을 정의합시다.

$S_k$ : k개의 색깔로 최소 비용을 만들수 있는 트리의 정점 개수의 최솟값

 

수열을 이렇게 정의하는 이유는 다음과 같습니다.

• $S_k=n$이면 1~n개의 정점을 가진 트리는 색깔을 $k$개 이하만 사용해서 최솟값을 만들 수 있습니다.
• 즉, 우리는 $S_k \geqslant 100,000$ 인 $k$를 찾으면 됩니다.

 

이제 k개의 색깔로 최소 비용을 만들수 있고, 정점 개수가 최소인 트리에 대해 생각해 봅시다.

색깔이 k인 정점이 항상 존재하므로 root를 색깔이 k인 임의의 정점으로 정합시다.

root의 색깔이 k이기 때문에 자식의 색깔들은 1~k-1이 모두 적어도 한번씩 등장해야 합니다.

정점 개수가 최소인 트리를 가정했으므로 1~k-1은 모두 각각 한번씩 등장하고, 색깔 개수가 $c$인 자식을 루트로 하는 서브트리의 크기는 $S_c$가 됩니다.

k개의 색깔로 최소 비용을 만들수 있고, 정점 개수가 최소인 트리

 

이제 점화식을 다음과 같이 세울 수 있습니다.

$$
S_k = S_1 + S_2 + \cdots + S_{k-2} + S_{k-1} + 1
$$

$S_1 = 1, S_2 = 2$ 이므로 일반항은 $S_k = 2^{k-1}$ 입니다.

 

그러므로 이 문제에서 사용되는 색깔 개수는 $\lceil \log_2100,000 \rceil$개 이하가 되고 [정점 번호][색깔]로 DP를 돌리면 됩니다.