백준 10422 파이썬 python : 괄호 @@황소처럼 우직하게@@ dp로 푸는 방법!!

올바른 괄호가 되기위해서는

( * * * * ) * * * * * * 

이런식.

이 때, 첫번째 괄호를 1번째, 두번째 괄호를 k 번째라고하자.

그러면 괄호안에 쌓여진 공간의 개수는 k - 2 이고, 오른쪽에 공간의 개수는 n - k 개이다.

dp[n] = dp[k - 2] * dp[n - k]  (k = 2 ~ n) 이다.

import sys
input = sys.stdin.readline

t = int(input())
lst = []
for _ in range(t):
    lst.append(int(input()))

dp = [0] * 5001
dp[0] = 1
for i in range(2, 5001, 2):
    for j in range(2, i + 1, 2):
        dp[i] += (dp[j - 2] * dp[i - j]) % 1000000007

for i in lst:
    print(dp[i] % 1000000007)