[Python] 백준 10422번: 괄호

https://www.acmicpc.net/problem/10422

10422번: 괄호

 '(' 괄호는 +1, ')' 괄호는 -1 로 계산하면 된다. 음수가 될경우 괄호가 아니므로 양수일때만 연산해준다.

	0	1	2	3	4	5	6	7	8
1		1
2	1		1
3		2		1
4	2		3		1
5		5		4		1
6	5		9		5		1
7		14		14		6		1
8	14		28		20		7		1

T = int(input())

mod = 1_000_000_007
dp = [[0 for _ in range(5002)] for _ in range(5002)]
dp[1][1] = 1
for i in range(1, 5000):
    for j in range(5001):
        if j == 0:
            dp[i+1][j+1] += dp[i][j] % mod
        elif j == 5000:
            dp[i+1][j-1] += dp[i][j] % mod
        else:
            dp[i+1][j+1] += dp[i][j] % mod
            dp[i+1][j-1] += dp[i][j] % mod
            
while T:
    T -= 1
    n = int(input())
    print(dp[n][0] % mod)