Jae-Kyung Cho Robotics and deep learning engineer

Baekjoon-10422-괄호

Dynamic 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)
Comments