[BOJ] 12995. 트리나라

문제 링크

풀이

$dp[v][k]$를 정점 $v$가 루트인 서브트리에서 정점 $v$를 포함하면서 이사할 도시 $k$개를 고르는 방법의 수로 정의하겠습니다. $k = 0$일 때는 $1$로 정의하도록 하죠. 그럼 아래와 같은 점화식을 구할 수 있습니다.

위 점화식을 사용하면 DFS로 트리를 탐색하면서 트리 DP를 하면 됩니다. 하지만 해당 점화식을 충분히 빠른시간에 계산해야 합니다. 어떻게 할 수 있을까요?

잘 생각해보면 다항식의 곱셈에서 위 점화식과 비슷한 식을 찾아볼 수 있습니다. $n$차 이하의 다항식 $k$개를 곱한다고 합시다. 각 다항식을 $P_{i}(x) = \displaystyle \sum_{i = 0}^{n} {a_i x^i}$라고 한다면 $k$개의 다항식을 곱한 결과는 아래와 같습니다.

$dp$의 점화식과 상당히 비슷합니다. 이를 이용해봅시다. $N$차 이하의 다항식 $P_{v}(x) = \displaystyle \sum_{k = 0}^{N} {dp[v][k] \cdot x^i}$로 정의 하겠습니다. 그러면 $dp[v][k]$는 $\displaystyle \prod_{v_i \in subtree(v)} {P_{v_i}(x)}$에서 $x^{k}$의 계수가 됩니다. 즉, 자식 정점에 해당하는 다항식을 전부 곱해서 나온 다항식을 통해서 현재 정점에 해당하는 $dp$값을 전부 구할 수 있습니다.

정점 하나의 $dp$값을 전부 구하기 위해서는 $N$차 이하의 다항식을 $N$개 미만 곱해야하므로 시간복잡도는 $O(N^3)$입니다. 정점이 총 $N$개이므로 전체 시간복잡도는 $O(N^4)$이 됩니다. $N \leq 50$이기 때문에 충분히 시간안에 돌 수 있습니다.