정 이진트리의 가짓수 세기
시간 제한2초메모리 제한128 MB
정확히 n개의 노드와 정확히 k인 높이를 가지는 모든 이진 트리의 개수를 9901로 나눈 나머지로 구하는 문제입니다.
문제
다음 조건을 모두 만족하는 서로 다른 이진트리의 개수를 구한다.
- 노드는 정확히 n개이다. (1 <= n < 200)
- 모든 노드의 차수는 0 또는 2이다. 여기서 차수는 한 노드가 가진 자식 노드의 개수이다.
- 트리의 높이는 정확히 k이다. (1 < k < 100) 높이는 루트에서 단말 노드까지 내려가는 경로 중 가장 긴 경로에 포함된 노드 수이다. 단말 노드는 자식이 없는 노드이다.
이진트리이므로 왼쪽 자식과 오른쪽 자식의 배치가 다르면 서로 다른 트리로 센다.
답이 매우 클 수 있으므로 9901로 나눈 나머지를 구한다.
입력
첫째 줄에 두 정수 n과 k가 주어진다.
출력
조건을 만족하는 서로 다른 이진트리의 개수를 9901로 나눈 나머지를 출력한다.