[10422] 괄호

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

10422번: 괄호

<문제>

dp를 채우는 방식이 독특한 문제, 홀수일 때에는 불가능하니 짝수일 때만 고려해주면 된다.

카탈란 수와 관련 있는 문제다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll M = 1e9 + 7;
ll t, n, dp[5001];
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i, j;
    dp[0] = dp[2] = 1;
    for (i = 4; i <= 5000; i += 2) {
        for (j = 2; j <= i; j += 2) {
            dp[i] += dp[j - 2] * dp[i - j];
            dp[i] %= M;
        }
    }
    cin >> t;
    while (t--) {
        cin >> n;
        if (n % 2 == 1)
            cout << "0\n";
        else
            cout << dp[n] % M << '\n';
    }
    return 0;
}