황소개발자

올바른 괄호가 되기위해서는 ( * * * * ) * * * * * * 이런식. 이 때, 첫번째 괄호를 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..