[알고리즘/백준] 10422번 : 괄호(python)

처음에는 뭔가 싶었다...
카탈란의 수 라는걸 쓰라고 하는데 이런거 쓰기 싫어서 그냥 dp로 풀려고 계속 해봤다.
전체를 N이라고 하면
무작위의 위치에 여는 괄호 하나가 나왔다고 하자. 그리고 그 괄호를 닫는 괄호의 위치를 i라고 하면
괄호 사이에 들어가 있는 괄호의 갯수는 i - 2개가 된다.
i부터 끝까지의 괄호의 갯수는 n - (i - 2) + 2
n - i가 나온다.

dp[n] = dp[i - 2] + dp[n - i]

N = int(input())
a = list(int(input()) for _ in range(N))
dp = [0] * (max(a) + 1)
dp[0] = 1

for n in range(2, max(a) + 1, 2):
    for j in range(2, n + 1, 2):
        dp[n] += dp[j - 2] * dp[n - j]
    dp[i] %= 1000000007
for i in a:
    print(dp[i])