10422

문제를 보자마자 DP를 써야 한다는건 직감했는데 식을 어떻게 세워야 할지 쉽게 감이 오지 않았다. 가장 직감적으로 들었던 식은 이렇다.

문자열의 길이가 K인 경우의 식은 아래와 같이 구할 수 있다고 생각했다.

1. dp[K] = dp[K-2]

2. dp[K] += dp[2]*dp[K-2] + dp[4]*dp[K-4] + ... dp[K-2]*dp[2]

이미 괄호의 개수가 정해진 K-2개의 문자열에 괄호를 끼운다고 생각하면 반드시 올바른 괄호가 되므로 1번 식은 성립한다. 2번 식은 나머지 경우들을 처리하는 식인데, K개의 괄호식을 만든다고 생각할 때 앞부분에 해당하는 괄호의 경우의 수 와 뒷부분에 해당하는 괄호의 경우의 수를 곱해주면 길이가 K인 문자열을 구할 수 있다고 생각했다. 하지만 위의 식은 중복되는 경우의 수들을 처리하지 못한다.

만약 위의 식으로 K=6인 경우를 구하면

dp[2] = 1, ()

dp[4] = 2, (()) ()()

1번식에 의해 dp[6] = 2    ->     ((())), (()())

2번식에 의해 dp[6] += dp[2]*dp[4]     ->     ()(()), ()()()

       + dp[4]*dp[2]    ->    (())(), ()()()

'()()()' 라는 중복된 경우가 생겨버린다. DP를 사용하면서 중복된 경우가 생기지 않도록 식을 만들어야한다.

K개의 문자열의 앞부분과 뒷부분을 크게 A와 B로 나뉘어보자. 2번식에 따르면 A의 크기는 점점 커지고, B의 크기는 점점 작아질 것이다.

만약 크기가 달라지면서 생기는 모든 A영역들에 대하여 중복된 경우가 없다고 할 수 있다면, B영역에 대해서 생각 할 필요 없이 위 문자열은 중복되지 않았다고 정의 할 수 있다.

B영역내에서 중복이 있든 없든 문자열 전체로 보면 A 영역내에서 이미 특수성을 가지고 있기 때문에 고려할 대상이 아니다.

중복하지 않는 각 A 영역의 경우의 수는 어떻게 구할 것이냐? 이건 1번식을 통해서 이미 구했다. 1번식은 바로 전 문자열에서 괄호 두 개를 덮은 것이기 때문에 길이가 달라도 중복된 것이 생기지 않는다고 할 수 있다.

위 방법으로 DP식을 다시 정리해보자.

1. dp[K][0] = dp[K-2][0] + dp[K-2][1]    -> 이전 문자열에 괄호를 씌운 경우

2. dp[K][1] = dp[2][0]*(dp[K-2][0] + dp[K-2][1]) + dp[4][0]*(dp[K-4][0] + dp[K-4][1]) ... + dp[K-2][0]*(dp[2][0] + dp[2][1])

 
#include <stdio.h>

using namespace std;

#define MAXN 5005
#define MOD 1000000007

long long dp[MAXN+1][2];

void init() {
	dp[2][0] = 1;

	for(int i=3; i <= MAXN; i++) {
		if(i%2)
			continue;
		for(int j=2; j<i; j+=2) {
			dp[i][1] = (dp[i][1] + dp[j][0]*dp[i-j][0])%MOD;
			dp[i][1] = (dp[i][1] + dp[j][0]*dp[i-j][1])%MOD;
		}
		dp[i][0] = (dp[i-2][0] + dp[i-2][1])%MOD;
	}
}

int main()
{
	freopen("input.txt", "r", stdin);

	int tc, inp;

	init();
	scanf("%d", &tc);

	while(tc--) {
		scanf("%d", &inp);
		printf("%lld\n", (dp[inp][0] + dp[inp][1])%MOD);
	}


	return 0;
}