백준 10422번 괄호

문제

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 가지가 있다.

하지만 우리가 궁금한 것은 길이가 L인 올바른 괄호 문자열의 개수이다. 길이 L이 주어졌을 때 길이가 L인 서로 다른 올바른 괄호 문자열의 개수를 출력하는 프로그램을 만들어 보자.

입력

첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000) 

출력

각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오.

 

DP는 진짜 어렵다.. 골드 정도만 되도 체감상 완탐이나 string 플레 정도 느낌..?

아이디어는 D[n]이 길이 n의 올바른 괄호 개수라면

( -------------------- )[               ]

처음의 여는 괄호에 대응되는 닫는 괄호가 i 번째에 위치한다면 그 안에 있는 ---------------------영역은 D[i-2]

그리고 [     ] 영역은 전체 n에서 i만큼 빠지므로 D[n - i]가 된다.

따라서 D[n] = D[i-2] * D[n - i]이고 

정답을 인정받으려면 n이 증가할수록 카운트가 급증하기 때문에 long long 자료형에

% 1,000,000,007을 한번에 해주면 이미 해주기 전에 값이 long long 범위를 초과하여 쓰레기 값이 되므로

매번 더해질때마다 해줘야 함.

#include<iostream>
#include <string.h>
#include<string>
#include<queue>
#include <vector>
#include<map>

using namespace std;

long long D[5001];
void init()
{
	D[0] = 1;
	D[2] = 1;

	for (int i = 3; i <= 5000; i++)
	{
		for (int j = 2; j <= i; j++)
		{
			D[i] += D[j - 2] * D[i - j];
		}
		D[i] %= 1000000007;
	}
}

int main(void)
{
	int tc;
	cin >> tc;
	
	init();

	for (int t = 0; t < tc; t++)
	{
		int n;
		cin >> n;
		cout << D[n] << endl;
	}
}