백준 10422 / 괄호

다이나믹 프로그래밍

점화식을 생각해내는 것이 굉장히 어렵다.

길이는 L 

d[n]가 길이 n에서 만들 수 있는 괄호 문자열의 개수라고 가정하자.

첫번째 (과 대응되는 )가 i번쨰 위치에 있다고 가정하자.

그렇다면 첫번째 (와 i번째 위치의 ) 사이엔 총 몇개의 경우의수가 있을까. d[i-2]

그리고 i 이후의 문자열엔 몇개의 경우의 수가 있을까. d[L-i]

그렇다면 L을 1부터 5000까지, i를 2부터 L까지 모든 경우에 대해

d[L]에 d[i-2] * d[L-i]를 더해줘야 한다.

내가 짠 코드엔 하나의 꼼수가 있는데 

d[0]을 1로 설정해야 제대로 된 정답이 출력된다는 점이다. 원래 d[0]은 0이어야한다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<math.h>
 
using namespace std;
 
long long d[5001];
 
int main() {
    //freopen("Text.txt", "r", stdin);
    
    int testcase;
    cin >> testcase;
 
    // -1 : 0 , 0 : 1 , 1 : 2
    d[0] = 1;
    d[2] = 1;
 
    for (int i = 3; i <= 5000; i++) {
        for (int j = 2; j <= i; j++) {
            
            if (j - 2 >= 0 && i - j>=0) {
                d[i] += d[j - 2] * d[i - j];
                d[i] = d[i] % 1000000007;
            }
        }
    }
 
    while (testcase--) {
        int n;
        cin >> n;        
        cout << d[n]<< endl;
    }
}