처음에는 뭔가 싶었다...
카탈란의 수 라는걸 쓰라고 하는데 이런거 쓰기 싫어서 그냥 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])
smilegate