한양대학교는 크리스마스 즈음이 되면 애지문에 트리를 꾸며 놓는다. 그리고 이번 년도에는 김하냥이 크리스마스 트리 꾸미기를 맡게 되었다. 하지만 김하냥은 트리라고는 이진트리 밖에 모르는 이진트리 바보이다. 그래서 김하냥은 애지문에 놓을 트리를 이진트리 모양으로 꾸미고 싶어 한다.
한양대에서는 김하냥에게 장식으로 '트리 볼'만을 제공한다. 하지만 이 볼의 개수에는 제한이 있고, 꾸며야 할 트리의 높이 또한 정해져 있다. 한양대에서 트리의 높이를 제한해 준다면, 김하냥은 꼭 그 트리 높이만큼의 트리를 만들어야 한다. 트리가 그 높이보다 작거나 클 수 없고, 볼도 한양대에서 제한해 준 개수로만 사용 가능하다. 또한 제공된 '트리 볼'도 반드시 모두 사용해야 한다.
김하냥은 볼의 개수와 트리의 높이에 제한이 있을 때, 자신이 트리를 꾸밀 수 있는 경우의 수가 궁금해졌다. 이진트리 밖에 모르는 김하냥을 위해 우리 한양대생들이 도와주자!
예를 들어, 볼의 개수가 5이고, 트리의 높이가 3이라면 트리를 꾸밀 수 있는 경우의 수는 다음과 같다.
첫째 줄에 볼의 개수 N과 트리의 높이 L이 차례대로 주어진다. (1 ≤ N ≤ 300, 1 ≤ L ≤ 300)
출력
트리를 꾸밀 수 있는 경우의 수를 100,030,001로 나눈 나머지를 출력한다.
입력 예시
5 3
출력 예시
6
풀이
DP 문제. 처음에는 막무가내로 O(L*N^3)의 시간복잡도로 풀이했다가 좌절을 맛보았다. 300^4는 매우 큰 수였다...
접근을 바꾸어, i개의 볼을 사용하고 최종 높이가 j인 트리의 경우의 수를 우리가 알고 있다고 하자. 우리는 새로운 트리를 만들때, 왼쪽 서브트리 + 오른쪽 서브트리 + 루트 형태로 만들 수 있다.
이 경우, 높이가 j+1인 트리를 만들기 위해서는 적어도 한 서브트리가 높이가 j여야 한다. 즉 다음 경우가 성립한다.
높이가 j인 서브트리와 높이가 j-1 이하인 서브트리를 배치한다. 좌우 순서가 바뀔 수 있으므로 2를 곱해주어야 한다.
높이가 j인 서브트리 둘을 배치한다. 좌우 순서가 자동적으로 고려되므로 단순히 더해주기만 하면 된다.
이렇게 풀이했을 때, 최종적으로 O(L*N^2)의 시간복잡도를 갖게 된다. 나는 j-1이하의 합 dp, j를 이루는 dp, j+1 결과인 dp 3가지를 갱신해나가는 방식을 사용했다. 하지만 핵심적인 접근법은 동일하게 가져가고 3차원 dp로도 풀 수 있는 것으로도 보인다.
풀이 코드
MOD = 100030001
N, L = map(int, input().split())
sum_dp = [0]*(N+1)
last_dp = [0]*(N+1)
sum_dp[0] = last_dp[1] = 1
for i in range(L-1) :
new_dp = [0]*(N+1)
for j in range(i+1, N+1) :
for k in range(N+1) :
if j + k + 1 > N :
break
new_dp[j+k+1] = (new_dp[j+k+1] + 2 * last_dp[j] * sum_dp[k]) % MOD
new_dp[j+k+1] = (new_dp[j+k+1] + last_dp[j] * last_dp[k]) % MOD
for j in range(N+1) :
sum_dp[j] = (sum_dp[j] + last_dp[j]) % MOD
last_dp = new_dp
print(last_dp[-1])
