백준 / 10422 괄호 C++

www.acmicpc.net/problem/10422

10422번: 괄호

간단한 dp 문제였습니다. 주어진 길이의 서로 다른 올바른 괄호의 개수를 구해라는 문제입니다.

올바른 괄호 : ( ), ( )( ) 등

 

괄호는 쌍이 존재해야하므로 입력이 홀수면 무조건 0개입니다.

 

주어진 길이가 5000 자리라고 하면 5000 자리는 ( 5천 자리, 완전히 감싸진 괄호 ), (2자리 괄호 개수)*(4998자리 괄호 개수), .... (4998자리 괄호 개수) * (2자리 괄호 개수) 로 쪼개서 생각할 수 있습니다. 

이를 이용해 짝수번째마다 재귀적으로 함수를 호출하여 길이 L인 가능한 개수 = dp[ L ] 이라 하면 (dp[0]=1)

for i=2 to i=L, i+=2:

  dp[ L ] += dp[i-2] * dp[L-i] 

라 할 수 있습니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int T, L;
unsigned long long mod = 1000000007;
unsigned long long dp[5001];

// 길이 Length인 가능한 괄호 개수 : dp
// 5천자리 괄호면 ((...5천자리...)),
// (2자리 괄호) * (4998자리 괄호) ~ (4998자리 괄호) * (2자리 괄호)
unsigned long long recur(int Length)
{
	// 통째로 감싸진 경우
	if (Length == 0)
		return 1;

	if (dp[Length] > 0)
		return dp[Length];

	for (int i = 2; i <= Length; i += 2)
	{
		dp[Length] += (recur(i - 2) * recur(Length - i));
		dp[Length] %= mod;
	}

	return dp[Length];
}

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

	cin >> T;
	while (T--) {
		cin >> L;
		if (L % 2 != 0)
			cout << 0 << '\n';
		else
			cout << recur(L) << '\n';
	}
}