[Python] 18132번 내 이진트리를 돌려줘!!!

https://www.acmicpc.net/problem/18132

18132번: 내 이진트리를 돌려줘!!!

---

 

23/12/06

 

 

이것도 유명한 카탈란 수의 유형 중 하나이다.

---

 

문제 접근 방식:

 

 

먼저 문제의 출력을 보자. 익숙한 숫자들이 보일 텐데, 여기서 카탈란 수임을 예측하고 구현하면 맞았습니다를 받을 수 있다.

 

그러면 이 문제의 점화식이 왜 카탈란 수가 나오는지 생각해보자.

 

우리는 이진트리가 주어진다면, 그 이진트리의 왼쪽에 있는 부분과 오른쪽에 있는 부분으로 트리를 "분리"하여 생각할 수 있다.

 

$N$개의 간선이 주어져 있을 때 만들 수 있는 트리의 경우의 수를 $C_n$이라고 해보자.

 

그러면, 이 트리가 왼쪽에 간선이 $i$개, 오른쪽에 간선이 총 $N-i$개 달려있는 트리라고 한다면 이 값이 $C_i * C_{N-i}$가 될 것이다.

 

원래 트리의 왼쪽에 간선이 $0$개부터 $N-1$개까지 올 수 있으므로, 이를 다 합산하게 된다면 트리의 경우의 수에 대한 점화식은 카탈란 수가 나온다는 사실을 확인할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 18132번 내 이진트리를 돌려줘!!!
# DP, 조합론
'''
접근 방법:
카탈란 수
'''
import sys
input = sys.stdin.readline

MOD = 1_000_000_007
Catalan = [0 for _ in range(5002)]
Catalan[0], Catalan[1] = 1, 1
for i in range(2, 5002):
    C = 0
    for j in range(i):
        C += (Catalan[j]*Catalan[i-j-1])%MOD
    C %= MOD
    Catalan[i] = C
for _ in range(int(input())):
    N = int(input())
    print(Catalan[N+1])