[Python] 10422번 괄호

 

 

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

10422번: 괄호

---

 

23/05/07

 

 

카탈란 수 기본 문제다.

---

 

문제 접근 방식:

 

 

조합론에서 카탈란 수는 매우 매우 매우 중요한 수 중 하나이다.

 

괄호 문제의 경우, 카탈란 수 예시 중 가장 첫 번째로 나오는 예시인 만큼 알아 두어야 할 것이다.

 

카탈란 수의 점화식을 그대로 구현하면 끝이다.

 

점화식은 다음과 같다.

 

$$C_n = C_0C_{n-1} + C_1C_{n-2} + \cdots + C_{n-1}C_0$$

---

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

# 10422번 괄호
# DP, 조합론
'''
접근 방법:
카탈란 수
'''
MOD = 1000000007
DP = [1]
for n in range(1, 2501):
    total = 0
    for i in range(n):
        total += DP[i]*DP[n-i-1]
        total %= MOD
    DP.append(total)
T = int(input())
for _ in range(T):
    L = int(input())
    if L%2 == 0:
        print(DP[L//2])
    else:
        print(0)