백준[1648] 격자판 채우기

문제 설명

문제 링크

http://icpc.me/1648

1648번: 격자판 채우기

풀이

비트 마스킹을 하며 dp를 돌면 풀 수 있다.

3 x 6 타일

위와 같은 타일이 있을 때, k 번째 타일을 놓기 위해 필요한 정보는 k + 1 번째 타일이 채워져 있는지 여부와 k + 6(m) 번째 타일이 채워져 있는지 여부이다.  이와 같이 k번째 타일을 채우기 위해서는 m개의 타일 정보만 가지고 있으면 된다. 그렇기 때문에 m개의 타일 정보를 비트 마스킹하며 채워나가면 된다.

코드

#include <cstdio>
#include <cstring>

int dp[15 * 15][1 << 14], n, m;
const int MOD = 9901;

int dpf(int k, int s) {
    if (k == n * m && !s) return 1;
    if (k >= n * m) return 0;
    int &ret = dp[k][s];
    if (~ret) return ret;
    ret = 0;
    if (s & 1) ret = dpf(k + 1, s >> 1);
    else {
        ret += dpf(k + 1, (s >> 1) | (1 << (m - 1)));
        if ((k % m) != (m - 1) && !(s & 2)) ret += dpf(k + 2, s >> 2);
    }
    return ret % MOD;
}

int main() {
    scanf("%d %d", &n, &m);
    memset(dp, -1, sizeof dp);
    printf("%d", dpf(0, 0));
}