1648번 격자판 채우기

https://www.acmicpc.net/problem/1648

공부 코딩 dp cache 다이나믹 동적 비트마스크 bit bitmask 캐시 생각 사고 논리 Tip 팁 boj 백준

참고(백준님 풀이 슬라이드와 코드)

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648

https://gist.github.com/Baekjoon/b575f09e963137fd2b1e

꼭 복습해야할 문제이다.

사진과 주석 참고.

hsdevppt1648.pptx

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 15
#define Mod 9901
 
int n, m, cache[Max * Max][1 << Max];
 
int go(int N, int S)
{
    // 마지막(=n*m)까지 왔는데 그 칸이 이미 채워져 있다면 return
    if (N == n*m && S == 0) {
        return 1;
    }
 
    if (N >= n*m) {
        return 0;
    }
 
    int &ret = cache[N][S];
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    if ((S & 1) == 1) {
        // 블록을 놓을 수 없는 경우 = 현재 칸이 비트에서 1인 경우 
        // 즉, S를 이진수로 나타냈을 때 마지막 비트가 1인 경우
        ret = go(N + 1, S >> 1);
        ret %= Mod;
    }
    else {
        // 2 X 1를 놓을 수 있는지 검사 → 현재 N이 비트가 안 켜져 있다면, 무조건 1 X 2를 놓을 수 있다.
        // 현재 N칸과 그 아래 칸에 대한 비트를 킬 것이다.
        // 현재 칸(N)에 대한 비트(=S)와 N+m칸에 있는 비트를 키고 다음 칸으로 이동할 것이라면,
        // 이미 S에는 N에 대한 상태 비트가 포함되어 있으므로 단순히 S | (1 << m)만 해주면 된다. : N+m칸 비트를 킴.
        // (S | (1 << m)) >> 1
        // 또는 이것도 된다. 다음 칸으로 이동해서 m - 1칸에 있는 비트를 킴: return go(N + 1, (S >> 1) | (1 << (m - 1)));
        ret = go(N + 1, (S | (1 << m)) >> 1);
        ret %= Mod;
 
        // 1 X 2을 놓을 수 있는지 검사 + 현재 N칸이 가장 오른쪽 칸인지 아닌지도 확인 필요
        // 사실 (S & 1) == 0은 이미 검사해서 필요없으나 공부를 위해 적음.
        // (N % m) + 1 != m은 가장 오른쪽 칸(열)인지 확인.
        if ((S & 1) == 0 && (S & 2) == 0 && (N % m) + 1 != m) {
            ret += go(N + 2, S >> 2); // 위에 것도 누적해야 하므로, =이 아니라 +=이다.
            ret %= Mod;
        }
    }
 
    return ret % Mod;
}
 
int main()
{
    cin.tie(0);
 
    memset(cache, -1, sizeof(cache));
 
    scanf("%d %d", &n, &m);
 
    printf("%d\n", go(0, 0));
 
    return 0;
}