[백준/BOJ] 10422번 괄호 (C++)

www.acmicpc.net/problem/10422

10422번: 괄호

DP 유형의 문제, 카탈린 수의 개념을 알고 있어야 함!

 

카탈린 수의 점화식은 아래와 같습니다.

카탈린 수

 

#include <iostream>
using namespace std;

long long dp[2501]; // n쌍의 올바른 괄호를 만들 수 있는 경우의 수

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    
    int T, L;
    long long answer;
    
    dp[0] = 1, dp[1] = 1;
    for(int i = 2; i <= 2500; i++) {
        for(int j = 0; j <= i - 1; j++) {
            dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % 1000000007; // 카탈린 수
        }
    }
    
    cin >> T;
    while(T--) {
        cin >> L;
        answer = L % 2 == 0 ? dp[L / 2] : 0;
        cout << answer << "\n";
    }
}