Baekjoon-10422-괄호
30 Sep 2022Dynamic programming으로 풀기
import sys
input = sys.stdin.readline
T = int(input())
Ls = [int(input()) for _ in range(T)]
max_L = max(Ls)
div = int(1000000007)
dp = [0] * (max_L+1)
dp[0] = 1 # for calculation
dp[2] = 1
for i in range(4,max_L+1,2):
for j in range(0,i-2+1,2):
dp[i] += dp[j] * dp[i-j-2]
for L in Ls:
print(dp[L] % div)
점화식 그냥 수학적으로 풀어서 계산하기 (카탈란 수)
ref:
it 공부 기록용 블로그:티스토리
카탈란 수 일반항
import math
def catalan(n):
return math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))
t = int(input())
n = []
for i in range(t):
n.append(int(input()))
for i in n:
if i % 2 == 1:
print(0)
else:
print(catalan(i//2)%1000000007)