[leetcode][96] Unique Binary Search Trees

문제 : https://leetcode.com/problems/unique-binary-search-trees/

---

1..n 의 수로 만들어질 수 있는 BST의 수를 구하라.

---

예시에서 보여주고 있는 n = 3일 때의 만들 수 있는 BST들을 노드 입력 순으로 나열해보자.

1. 1 2 3
2. 1 3 2
3. 2 1 3 (2 3 1)
4. 3 2 1
5. 3 1 2
        

3번을 보면 [2, 1, 3] 과 [2, 3, 1]의 BST 결과가 같다는 것을 알 수 있다.

BST는 루트노드보다 작은 노드들은 루트노드의 왼쪽 서브트리로 가고, 루트노드보다 큰 노드들은 루트노드의 오른쪽 서브트리로 간다.

그러므로 2 다음에 1이나올지 3이 나올지는 중요하지 않다는 것이다. 1은 반드시 2의 왼쪽 서브트리로 갈 것이고, 3은 반드시 2의 오른쪽 서브트리로 갈 것이기 때문이다.

즉, 이 문제는 루트 노드로 할 수를 정하고 그 루트 노드 보다 작은 수들이 왼쪽서브트리를 만들 수 있는 방법, 루트노드보다 큰 수들이 오른쪽 서브트리를 만들수 있는 경우의 수의 곱을 구해야 한다.

 

만약 n이 5일 때, 루트 노드를 2라고 하면 오른쪽 서브트리를 구성하는 노드들은 3, 4, 5가 된다. BST를 만들때 노드간 수 비교는 어차피 상대적이므로 3, 4, 5를 1, 2, 3으로 봐도 무방하다. 즉, 어떤 수들이 가는게 중요한게 아니고 몇 개의 노드들이 서브트리를 이루는지가 중요하다.

 

dp[n] = sum(dp[root-1] * dp[n-root]) (1 <= root <= n)

위 생각으로 점화식을 짜보면 위와 같다. dp[n]은 1..n으로 만들 수 있는 BST의 수다.

root 노드가 될 수 있는 수는 1 ~ n이고 root를 기준으로 왼쪽(root-1 개), 오른쪽(n-root 개) 서브트리를 이루는 노드들의 수로 몇 개의 서브트리를 만들 수 있는지 구한다.

dp[0] = dp[1] = 1 이다. 0개의 노드로 만들 수 있는 BST 수는 0이지만 곱셈을 해주기 때문에 1로 한다. 

메모이제이션 해줘야 한다. (아니면 노드의 수가 중요하기 때문에 이미 구한 것도 중복으로 구하기 때문에 시간 낭비다.)

 

시간복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/96.%20Unique%20Binary%20Search%20Trees.cpp

---

 

문제가 괜찮구먼