[코드트리/INTERMEDIATE LOW] DP 서로 다른 BST 개수 세기 Python 파이썬

 

목차

 

 

 

🔥 문제 링크

https://www.codetree.ai/missions/2/problems/number-of-unique-bst?utm_source=clipboard&utm_medium=text 

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

 

 

 

🔥 문제 

 

🔥 풀이

dp에 뭘 채워넣어야 할지 고민을 많이 했다

✅ 이진탐색트리(BST)는 반드시 왼쪽수가 root보다 작아야 하고 오른쪽 수가 root보다 커야 하므로, 1부터 n까지 루트로 설정하며 (오른쪽에 올 수 있는 경우의 수)*(왼쪽에 올 수 있는 경우의수)를 배열에 더해주어 그 경우의 수를 dp에 채워넣어 이용하면 된다

✅ n=4일 때를 가정해보면 root로 돌아야 하는 수는 1, 2, 3, 4이다

✔️ root = 1 : 1보다 작은 수가 존재할 수는 없으므로 dp[0] * 1보다 큰 수가 3개 존재하므로 dp[3]

✔️ root = 2 : 2보다 작은 수는 1개 존재하므로 dp[1] * 2보다 큰 수가 2개 존재하므로 dp[2]

✔️ root = 3 : 3보다 작은 수는 2개 존재하므로 dp[2] * 3보다 큰 수가 1개 존재하므로 dp[1]

✔️ root = 4 : 4보다 작은 수는 3개 존재하므로 dp[3] * 4보다 큰 수가 0개 존재하므로 dp[0]

✔️ dp[4] = (dp[0] * dp[3])  + (dp[1] * dp[2]) + (dp[2] * dp[1])  +  (dp[3] * dp[0]) = 14

 

✅ 점화식

dp[n] +=

for root in range(1, n+1): #root를 1부터 n까지 설정

dp[root-1] *dp[n-root] 

 

 

🔥 코드

def get_bst(n):
    cnt = 0

    for i in range(1, n+1):
        cnt += dp[i-1] * dp[n-i]

    return cnt

n = int(input())

dp = [0]*20

dp[0] = dp[1] = 1

for i in range(2, n+1):
    dp[i] = get_bst(i)


print(dp[n])