(c++)백준 10422번: 괄호

www.acmicpc.net/problem/10422

10422번: 괄호

[풀이]

재귀 DP로 풀 수 있는 문제였다.

DP[x]: 길이 x인 올바른 괄호 문자열의 개수

#include <iostream>
#include <cstring>
using namespace std;

int T, L;
long long DP[5001];

long long solution(int len) {
	//길이가 0이 될 때까지 재귀 돌렸으면
	if (len == 0)
		return 1;
	long long& res = DP[len];
	//이미 길이 len에 대한 개수를 구했으면
	if (res >= 0)
		return res;
	res = 0;
	for (int i = 0; i <= len; i+=2) {
		res += solution(i)*solution(len - i - 2);
		//메모리 초과 안 나게 계산할 때마다 %해주기 
		res %= 1000000007LL;
	}
	return res;
}

int main() {
	cin >> T;
	memset(DP, -1, sizeof(DP));
	while (T--) {
		cin >> L;
		if (L % 2 == 1)
			cout << 0 << '\n';
		else
			cout << solution(L) << '\n';
	}
	return 0;
}