[백준] 10422번 - 괄호 / C++

문제

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

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

 

입력

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

 

출력

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

 

코드

#include <iostream>

#define MOD	1000000007

using namespace std;

long long m[5001];

void init()
{
	int i, j;

	m[0] = 1;
	for (i = 2; i <= 5000; i += 2)
	{
		for (j = 2; j <= i; j += 2)
		{
			m[i] += m[j - 2] * m[i - j];
			m[i] %= MOD;
		}
	}
}

int main()
{
	int t, T, L;

	init();
	cin >> T;
	for (t = 0; t < T; t++)
	{
		cin >> L;
		cout << m[L] << endl;
	}
	return 0;
}

 

괄호는 "()"가 한 쌍이므로 올바른 괄호가 되려면 문자열의 길이는 무조건 짝수여야 한다. 따라서 짝수 길이의 문자열에 대해 올바른 괄호의 수를 계산해준다.

올바른 괄호인 문자열은 괄호를 여는 것부터 시작해야 하므로 첫 번째 문자는 무조건 "("가 된다. 이 괄호는 바로 닫힐 수도 있고, 맨 마지막에 닫힐 수도 있다. 괄호가 닫히는 위치에 따라서 그 괄호 안과 괄호 밖의 하위 문자열로 나눌 수 있다. L = 8일 때를 예로 들어보자.

처음 열린 괄호가 두 번째 위치에서 바로 닫힌다면 이 괄호 안의 하위 문자열의 길이는 (2 - 2 = 0)이고, 괄호 밖의 하위 문자열의 길이는 (8 - 2 = 6)이다. 이제 각각의 하위 문자열을 어떻게 나타낼지만 고려하면 된다. 문자열의 길이가 0인 경우는 비어있는 경우 1가지이고, 문자열의 길이가 6인 경우는 이전에 계산한 값에 따라 5가지이다. 따라서 첫 괄호가 바로 닫히는 경우 올바른 괄호의 개수는 5가지 중에 1가지를 고르는 방법의 수인 5가 된다.

init()에서 i = 8이고 j = 2인 경우

처음 열린 괄호가 세 번째 위치에서 닫히는 경우에는 하위 문자열의 길이가 홀수가 되어 전체 문자열이 올바른 괄호가 될 수 없다. 같은 이유로 홀수번째 위치에서 닫히는 괄호는 올바른 괄호가 될 수 없기 때문에 고려하지 않는다.

처음 열린 괄호가 네 번째 위치에서 닫힌다면 괄호 안의 하위 문자열의 길이는 (4 - 2 = 2)이고, 괄호 밖의 하위 문자열의 길이는 (8 - 4 = 4)이다. 따라서 길이가 2인 올바른 괄호를 만드는 방법의 수와 길이가 4인 올바른 괄호를 만드는 방법의 수를 곱하면 모든 조합을 포함하게 된다.

init()에서 i = 8이고, j = 4인 경우

init()에서 i = 8이고, j = 6인 경우

init()에서 i = 8이고, j = 8인 경우

마찬가지로 모든 길이 L에 대해 올바른 괄호의 개수를 구할 수 있다.

 

링크

10422번: 괄호

inbdni/Baekjoon