안녕하세요,
재재입니다.
BOJ 1836 트리의 가짓수 세기 문제 풀이입니다.
BOJ 1836 트리의 가짓수 세기
(1) 문제 설명
분류 : dynamic programming, tree
출처 : https://www.acmicpc.net/problem/1836
(200 이하) N 개의 노드로 구성되고 (100 이하) K 의 depth 를 갖는,
이진 트리의 갯수를 구해주면 됩니다.
(2) 풀이 도출
상태공간을 먼저 정의해볼게요.
dp[n][k] : n 개의 node 를 사용하고, depth 가 k인 이진 트리의 갯수
이제 점화식을 세우기 전에 생각해봐야 하는게 있습니다.
- 현재 트리를 나누는 것이 가능한가?
- 나누었을 때 두 트리의 depth 후보군은 몇인가?
위의 2가지를 충분히 생각해보셨다면,
점화식을 세울 수 있습니다.
$$ dp[n][k] = \sum dp[i][k_i] * dp[n-1-i][k_j] $$
여기서, $$ k_i, k_j $$ 에 어떤 값을 넣으면 되는지 생각해보면,
아래와 같이 나뉘어집니다.
- depth 가 둘 모두 k-1 을 갖는 경우
- 좌측 subtree 는 k-1 이고, 우측 subtree 는 k-1 보다 작은 값을 갖는 경우
- 우측 subtree 는 k-1 이고, …
이에 대한 시간 복잡도는 다음과 같습니다.
$$ O(n^2k^2) $$
(3) 정답 코드
아래 코드에서 12번째 라인은,
위에 언급드렸던 트리를 구성할 수 없는 경우를 early return 하면서,
시간을 개선하였습니다.
그리고, modular 연산은 덧셈과 곱셈에 대해 닫혀 있습니다.
(4) 1836 시간복잡도 개선 포인트 제안
위의 점화식에서 사용한 상태공간의 정의를 조금 더 구체적으로 작성해볼게요.
dp[n][k] : 노드를 n 개 사용하고, tree 의 최대 depth 가 k 인 경우의 수
이 상태공간의 정의를 다르게 정의해서도 해결 할 수 있을 것 같은데요.
바로 아래와 같이 생각해 볼 수 있습니다.
dp[n][k] : node 를 n 개 사용하고, tree 의 depth 가 k 이하인 경우의 수
이제, 이 상태공간을 사용하고 여기에 포함 배제 원리를 적용하면,
sub_k 에 대해 탐색 할 필요가 없어지고,
시간복잡도는 아마도 $$ O(nk) $$ 에 해결 할 수 있어보입니다.