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

문제링크 : https://www.acmicpc.net/problem/10422

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD	1000000007

long long arr[5001];

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T, N;
    cin >> T;

    arr[0]=1; //빈 문자열
    for(int i=2; i<5001; i+=2) //짝수만 가능
    {
        for(int j=2; j<=i; j+=2)
        {
            arr[i] += arr[j-2] * arr[i-j];
            arr[i]%=MOD;
        }
    }

    for(int i=0; i<T; i++) 
    {
        cin >> N;
        cout << arr[N] << "\n";
    }

    return 0;
}

 

우선 올바른 괄호 문자열은 특성상 짝수만 가능하다.

그리고 구역을 2개 나눠서 생각할 필요가 있다.

일단 간단하게 초기값을 알아보면 다음과 같다.

N = 2
()

N = 4
()(), (())

 

N = 4인 케이스를 보면, 바로 올바른 문자열을 사용한 ()() 경우와 () 안에 올바른 문자열을 조합한 (()) 경우가 있다.

이를 2가지 구간으로 나눠보자.

N = 4

()..
()안에 가능한 문자열 길이 없음 -> arr[0]
..에 가능한 문자열 길이 2 = 직전에 구한 arr[2]의 값 = 1
따라서 가능한 조합은 arr[0]*arr[2]

(..)
안에 가능한 문자열의 길이 2
-> 직전에 구한 arr[2]의 값 = 1
남는 길이 없음 = arr[0]
따라서 가능한 조합은 arr[2] * arr[0]

 

이렇듯 직전에 구한 값을 이용해 값을 조합하는 것을 볼 수 있다.

N = 6의 케이스를 통해 더 자세히 살펴보자.

N = 6

()....
arr[0] * arr[4]
()안에 가능한 문자열 길이 없음 -> arr[0]
....에 가능한 조합 직전에 구한 값 -> arr[4]
따라서 가능한 조합은 arr[0] * arr[4]

(..)..
arr[2] * arr[2]
()안에 가능한 문자열 길이 2 -> arr[2]
..에 가능한 문자열 길이 2 -> arr[2]
따라서 가능한 조합은 arr[2] * arr[2]

(....)
arr[4] * arr[0]
()안에 가능한 문자열 길이 4 -> arr[4]
나머지에 가능한 문자열 길이 없음 -> arr[0]
따라서 가능한 조합은 arr[4] * arr[0]

 

규칙을 보면 앞에는 0부터 2씩 증가, 뒤는 2씩 감소한다.

따라서 2중 반복문을 통해 i, j값을 조절해 DP식을 세워주면 된다.

또한 짝수만 가능하기에 인덱스는 2씩 증가시켜주어야만 한다.

점화식

for(int i=2; i<5001; i+=2) //짝수만 가능
{
    for(int j=2; j<=i; j+=2)
    {
        arr[i] += arr[j-2] * arr[i-j]; //j 0부터 2씩 증가, i 증가하는 j만큼 감소 (2씩)
        arr[i]%=MOD;
    }
}