BOJ 1836 트리의 가짓수 세기

문제에 주어진 성질을 만족하는 서로 다른 이진트리의 개수를 구하는 문제인데,
주어진 조건은 다음과 같다.
1. n개의 노드를 갖는다.
2. 각 노드의 차수는 0또는 2이다.(차수는 자식노드의 개수, 즉 full binary tree를 말하는 것!)
3. 높이는 k인데, 이 문제에서 높이란 루트에서 단말노드(자식이 없는 노드)에 이르는 임의의 가장 긴 경로위에 존재하는 노드의 개수이다.

위의 조건을 만족하는 이진트리의 개수를 9901로 나눠서 출력하는 문제이다.
dp같아 보인다. 입력으로 n과 k가 주어지는데, d[n][k]=노드의 개수가 n이고, 높이가 k인 트리의 개수라고 하면 d[n][k]=...음 k가 높이인데, d[0~n-1][k-1]*d[n-1~0][..]높이를 설정하는 부분이 까다롭다... 이렇게 설정하는 것이 아닌가? 아 dp잘하려면 생각을 많이 해봐야 하는데, 생각을 거의 안 하니.. 일단은 이 정도 정리하고 다음 문제로 넘어가야겠다.

백준님 풀이 ---------------------------------------------------------------------

d[n][k]는 맞는데, k개이하의 높이로 설정해야 한다.

여기서 잠깐! 경우의 수 구하는 dp 유형에는 이렇게 크게 3가지가 있다고 한다.
1. 진짜 N개 구하는 경우
2. D[n]을 n개이하로 놓고 구하는 경우 -> D[n]-D[n-1]이 답! ***엄청난 방법이다...
3. 반대인 경우(구하는 경우의 여집합)를 구해서 전체에서 빼는 경우.(여집합을 구하기가 더 쉬울 때!)
---------------------------------------------------------------------------------

d[n][k] = 노드의 개수가 n이고 높이가 k인 트리의 개수
로 놓으면... root에서 단말 노드까지의 모든 경로가 다 k일 필요는 없고, 그 중 하나 이상만 k이면 되기 때문에 문제를 나눌 때, 경우의 수가 많아지고, 복잡해진다.

그래서 이 문제는 d[n][k] = 노드의 개수가 n이고, 높이가 k이하인 트리의 개수
로 놓아야 하고, 구하는 것은 d[n][k]-d[n][k-1]이 될 것이다. 진짜 생각을 조금만 바꾼, 관점을 조금 바꿔서 보는 것인데... 엄청난 것 같다. 어떻게 이런 생각을...

자 이제 생각을 해보자. 부분 문제를 어떻게 설정할 것인가? full binary tree이므로 트리를 만들 때 자식 노드가 2개씩 늘어나게 되는데, 그래서 노드의 개수는 홀수일 수 밖에 없다.
그리고 하나의 루트를 정하면, 그 자식 노드를 각각 루트로 하는 두 개의 sub tree가 존재할 텐데, 그 sub tree의 노드 개수도 각각 홀수개일 것이다.

그럼 루트노드를 하나 놓고, 시작해서 루트 아래의 서브 트리의 노드 개수를 홀수개로 주고, 높이는 k-1한 값 이하가 되도록 하면 될 것이다.

d[n][k]=SUM( x=1 ~ n-2, x는 홀수 / d[x][k-1]*d[n-1-x][k-1] ) 가 될 것이다.

문제에서 9901로 나눈 나머지를 출력하라고 했으므로 d[n][k]-d[n][k-1]이 음수가 나올 수 가 있다. 그렇기 때문에 마지막에 출력할 때 (d[n][k]-d[n][k-1]+9901)%9901 해줘야 한다.

AC를 받았다. 그런데, 백준님 코드와 비교해보니 내가 기저 사례를 처리할 때, k==1인 경우를 처리하지 않았다...처리하지 않으면 k가 음수로도 갈 수 있을 것 같은데.. 음 일단 AC는 받았지만 데이터가 적을 수 있으므로... k==1인 경우 처리하는 것을 추가해야 한다.