BOJ_10422 : 괄호

문제

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

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

입력

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

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#define mod 1'000'000'007

using namespace std;

int main() {
	
	int t;
	cin >> t;
	while (t--) {

		int n;
		cin >> n;
		if (n % 2 != 0) {
			cout << 0 << '\n';
			continue;
		}
		vector< vector<int> > d(n, vector<int>(n / 2 + 1, 0));
		d[0][1] = 1;
		// 시작은 무조건 "("

		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= n / 2; j++) {
				if (d[i - 1][j] == 0) continue;
				if (j > n - i) break;

				if (j - 1 >= 0) {
					d[i][j - 1] = (d[i][j - 1] + d[i - 1][j]) % mod;
				}
				if (j + 1 <= n / 2) {
					d[i][j + 1] = (d[i][j + 1] + d[i - 1][j]) % mod;
				}
			}

		}
		cout << d[n - 1][0] << '\n';



	}
	
	return 0;
}