1648번: 격자판 채우기 - DP(비트마스크)

1.

격자판의 각 칸을 왼쪽 위에서부터 \(0, 1, 2, ... , N*M-1\)이라 하자.

 

0	1	2	...
		...	\(K\)	x	x	x
x	x	x	x
						\(N*M-1\)

 

 

\(K\)번 칸 이전은 전부 격자를 채웠다고 가정하고 \(K\)번 칸에 주목해보자. 저 칸에 격자를 놓는 경우는 3가지다.

 

1. 이미 \(K\)번 격자가 채워져 있어서 격자를 놓을 수 없다.

2. 격자를 가로로 놓는다.

3. 격자를 세로로 놓는다.

 

위 세 경우 모두 'x'친 구간에만 영향을 받는다. 따라서 저 'x'친 구간을 하나의 집합으로 관리하며, 집합의 상태에 따라 앞으로 격자를 놓는 경우의 수가 얼마인지 계산해 나가면 문제를 해결할 수 있다. \(K\)번 칸 이후에 격자를 놓을 수 있는 경우의 수(큰 문제)는 \(K+1\)번 칸 이후에 격자를 놓을 수 있는 경우의 수(작은 문제)를 구하면 알 수 있으므로, 이 문제는 DP로 해결할 수 있다. 'x'친 구간을 하나의 집합으로 관리하는 것은 비트마스크로 하면 좋을 것이다.

 

 

2.

점화식은 다음과 같다.

 

\(dp[n][s]\) : 보고 있는 칸이 \(n\)이고, 칸 \(n\)을 기준으로 'x'친 구간의 상태가 \(s\)일 때, 격자를 채우는 경우의 수

 

위의 3가지 경우를 식으로 나타내 보자.

 

1. 격자를 놓을 수 없으므로 해당 칸은 건너뛴다. 결국 'x'친 구간을 한 칸씩 앞으로 당긴 셈이므로 식은 다음과 같다.

 

\(dp[n][s] = dp[n+1][s >> 1]\)

 

2. 격자를 가로로 놓으면 그 다음 칸은 못 쓴다. 결국 'x'친 구간을 두 칸씩 앞으로 당긴 셈이므로 식은 다음과 같다.

 

\(dp[n][s] = dp[n+2][s >> 2]\)

 

3. 격자를 세로로 놓으면 'x'친 구간의 \(M-1\)번째 칸을 채운 셈이다. 그와 동시에 'x'친 구간을 한 칸씩 앞으로 당기므로 식은 다음과 같다.

 

\(dp[n][s] = dp[n+1][(s >> 1) | (1 << (M-1))]\)

 

이 세 가지 경우를 종합해 DP를 짜면 문제를 해결할 수 있다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MOD = 9901;
int N, M;
ll dp[256][1 << 14];

ll solve(int n, int s)
{
    if(n == N*M) return s == 0;
    if(dp[n][s] != -1) return dp[n][s];
    
    ll& ret = dp[n][s];
    ret = 0;
    
    if(s & (1 << 0)) ret += solve(n+1, s >> 1);
    else
    {
        if(!(s & (1 << 1)) && n % M != M-1) ret += solve(n+2, s >> 2);
        //다음 칸이 비어 있거나, 현재의 칸이 맨 오른쪽 칸이 아니라면...
        ret += solve(n+1, (s >> 1) | (1 << (M-1)));
    }
    return ret %= MOD;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	memset(dp, -1, sizeof(dp));
	cout << solve(0, 0);
}