[BAE/<JOON> 문제풀이] 10422. 괄호

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

10422번: 괄호

 

핵심::

카탈랑 수열 문제

 

풀이::

괄호는 쌍을 이루어야만 올바른 괄호 문자열일 수 있으므로 입력된 N이 홀수인 경우 항상 0이다.

 

작은 N의 경우들을 계산해보면 (N / 2) + 1 번째 카탈랑 수를 출력해야함을 알 수 있다.

 

의견::

 

코드::

#include <iostream>

using namespace std;

const long long vvv = 1000000007;

long long dp[2510];

int main()
{
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= 2510; i++) {
        dp[i] = 0;
        for (int j = 1; j < i; j++) {
            dp[i] += (dp[j] * dp[i - j]) % vvv;
            dp[i] %= vvv; 
        }
    }
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;        
        cin >> n;

        if (n % 2 == 1) {
            cout << 0 << "\n";
            continue;
        }

        n /= 2;        
        cout << dp[n + 1] << "\n";
    }

    return 0;
}