백준[baekjoon] 1390

#include<cstdio>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

int n;
int dp[900][1 << 9];
int pattern[17][4] = { {0,1,3,4},{1,2,3,4},{0,3,4,7},{0,1,4,5},{1,3,4,6},
					   {1,3,4,5},{0,3,4,6},{0,1,2,4},{1,3,4,7},{2,3,4,5},
					   {0,3,6,7},{0,1,2,3},{0,1,4,7},{0,1,2,5},{1,4,6,7},
					   {0,3,4,5},{0,1,3,6} };
int width[17] = { 2,3,2,3,2,
				  3,2,3,2,3,
				  2,3,2,3,2,
				  3,2 };
int height[17] = { 2,2,3,2,3,
				   2,3,2,3,2,
				   3,2,3,2,3,
				   2,3 };

int solve(int num, int state) {

	if (num == 3 * n) {
		return 1;
	}

	int& ret = dp[num][state];
	if (ret != -1) return ret;

	ret = 0;


	int numPos = num % 3;
	int level = num / 3;
	for (int iter = 0; iter < 17; iter++) {

		int startNum = pattern[iter][0];

		if (level + height[iter] > n) continue;
		if (numPos == 0) {
			if (startNum != numPos) continue;
		}
		else if (numPos == 2) {
			if (startNum == 0 || (startNum == 1 && width[iter] >= 3)) continue;

		}
		else {
			if (startNum != 1 && width[iter] >= 3) continue;
		}

		bool isPossible = true;

		for (int i = 0; i < 4; i++) {
			if (state & (1 << (pattern[iter][i] - startNum))) {
				isPossible = false;
				break;
			}
		}
		if (!isPossible) continue;


		int nextState = state;
		for (int i = 0; i < 4; i++) {
			nextState |= (1 << (pattern[iter][i] - startNum));
		}
		int next;
		for (int i = 1; i <= 8; i++) {
			if (!(nextState & (1 << i))) {
				next = i;
				break;
			}
		}

		ret += solve(num + next, nextState >> next);
		ret %= 1000000;


	}

	return ret;
}

int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);

	printf("%d", (3 * n) % 4 == 0 ? solve(0, 0) : 0);

	return 0;

}