BOJ 21002 - Cactus

BOJ 21002 - Cactus

$dp(n,k)=$ 노드 $n$개가 있는 싸이클에서 이웃한 노드끼리 동일한 색상을 갖지 않고 $k$개의 색을 갖고 칠할 수 있는 경우의 수라고 하자.

예외적으로 $dp(1,k)=dp(2,k)=k,~~dp(3,k)=k \cdot (k-1) \cdot (k-2)$ 라 하자.

$dp(n,k)=k \cdot (k-1)^{n-1} - dp(n-1,k) ~~(n \ge 4)$ 이다.

왜냐면 싸이클이 아닌 일자로 된$n$개를 $k$개의 색으로 칠하는 경우의 수에서 $n-1$ 개의 정점중 첫 정점과 마지막 정점이 같은 색인 경우의 수를 빼면 되기 때문이다.

싸이클을 찾을 때마다 그 싸이클의 정점의 수가 $V$라면 $dp(V,k) \cdot \dfrac {k-1}k$ 만큼 정답에 곱해준다.

싸이클에 속하지 않은 모든 정점은 정답에 $k-1$ 을 곱해주고, 마지막에 $\dfrac k{k-1}$ 를 한 번 곱해주면 된다.

트리의 시작점은 항상 $k$개를 고를 수 있기 때문이라고 생각하면 된다.