[백준/BOJ/1648] 격자 채우기

#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 9901;
int N, M, dp[15*15][1 << 14 + 1];
int dfs(int num, int status) {
	if (num == N * M && status == 0) return 1;
	if (num >= N * M) return 0;
	int &ret = dp[num][status];
	if (ret != -1) return ret;
	ret = 0;
	if (status & 1) {
		ret = dfs(num + 1, status >> 1);
	}
	else {
		// 세로 채우기
		ret = dfs(num + 1, (status >> 1) | (1 << (M - 1)));
		// 가장 오른쪽 검사, 오른쪽칸 비어있는지 유무 확인
		if ((num % M) != (M-1) && (status & 2) == 0) {
			// 가로 채우기
			ret += dfs(num + 2, (status >> 2));
		}
	}
	return ret %= MOD;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 0) << "\n";
	return 0;
}