level - medium
[문제 내용]
1부터 n까지의 숫자로 구성된 BST 의 개수를 반환
[example 1]
Input: n = 3
Output: 5[exmaple 2]
Input: n = 1
Output: 1[해결 방법]
n이 1일 경우 개수 1
n이 2일 경우 개수 2
n이 3일 경우 개수 5
여기서 3일 경우를 좀더 보면,
왼쪽에 자식 node로 2개를 둘경우
위에서 언급한 n이 2일 경우의 개수만큼 존재하고,
왼쪽, 오른쪽 각각 한개씩 둘경우
n이 1일 경우가 두번 존재하는 것이고,
오른쪽에 자식 node로 2개를 둘경우도
n이 2일 경우의 개수만큼 존재하게 된다.
그래서 계산해보면
2(왼쪽에 2개) + (1 + 1)(왼쪽, 오른쪽 1개) + 2(오른쪽에 2개)
이렇게 되게 된다.
n이 4일 경우도 위와 같이
자식 node의 개수를 이용해 이전에 계산해둔 경우의 수를 얻어서
각각 더해주면 된다.
위의 내용을 코드로 작성하면
아래와 같이 된다.
class Solution {
public int numTrees(int n) {
int[] child = new int[n+1];
child[0] = 1; // 0 일경우도 1, 0으로 설정할 경우 곱하면 모두 0이 됨으로..
child[1] = 1; // 1 일경우 1
// 0과 1은 채웠으므로 2부터 시작
for(int i=2; i<=n; i++) {
int count = 0;
// root node에 대한 값
for(int j=1; j<=i; j++) {
int left = j - 1; // 왼쪽 node 개수
int right = i - j; // 오른쪽 node 개수
count += child[left] * child[right]; // 왼쪽 * 오른쪽 = 모든 경우의 수
}
child[i] = count; // node 의 개수가 i개 인 경우의 총 개수
}
return child[n];
}
}