BOJ)10422 괄호

문제: icpc.me/10422

괄호 문자열이 되려면 괄호 문자열이 채워져 나가는 과정에서 )의 개수가 (개수보다 많으면 안된다.

이를 만족하면서 채워져 나가는 길이가 N인 괄호문자열의 개수를 다이나믹 프로그래밍을 이용하여 구해주면 된다.

N이 홀수인 경우 0을 출력하고 N이 짝수인 경우 dp[n/2][n/2]를 출력하면 된다.

dp[x][y]의 정의는 (가 x개 )가 y개 까지 그려진 괄호문자열의 개수 이다.

점화식은 dp[x][y]=dp[x-1][y]+dp[x][y-1]이 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
typedef long long ll;
using namespace std;
ll dp[5001][5001];
ll t, n;
ll func(int x, int y) {
    if (x < y)return 0;
    if (x < 0 || y < 0)return 0;
    if (x == 0 && y == 0)return 1;
    ll &ret = dp[x][y];
    if (ret != -1)return ret;
    ret = 0;
    ret += func(x - 1, y) + func(x, y - 1);
    ret %= MOD;
    return ret;
}
int main() {
    scanf("%lld", &t);
    memset(dp, -1, sizeof(dp));
    while (t--) {
        scanf("%lld", &n);
        if (n % 2)puts("0");
        else
            printf("%lld\n", func(n / 2, n / 2));
    }
    return 0;
}