[코드트리/INTERMEDIATE LOW] 서로 다른 BST 개수 세기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• DP (Tabulation)

. BST(1), BST(2)부터 시작해 BST(n) 구하기

- 서로 다른 BST 개수

 = (왼쪽에 들어갈 수로 만들 수 있는 서로 다른 BST 개수) * (오른쪽에 들어갈 수로 만들 수 있는 서로 다른 BST 개수)

 

→ (왼쪽, 오른쪽 쌍) = (0, n-1), (1, n -2), (2, n-3), ...

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        
        int[] dp = new int[N + 1];
        dp[0] = 1;
        dp[1] = 1;
 
        for(int i = 2 ; i <= N ; i++) {
            int sum = 0;            
            for(int j = 0 ; j < i ; j++) {
                sum += dp[j] * dp[i - j - 1];   // 왼쪽 BST 경우의 수 * 오른쪽 BST 경우의 수
            }
            dp[i] = sum;
        }
 
        System.out.println(dp[N]);
    }
}

 

 

 

---

💦 어려웠던 점

오.. 혼자 절대 이 식을 생각해내지 못 했을 것 같다,,

담엔 BST 스스로 셀 수 있길,,,

 

 

🧐 새로 알게 된 내용

DP로 BST 만드는 식

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리