BOJ 1648 격자판 채우기

문제

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

N*M 크기의 격자판을 2*1 모양의 타일로 채우는 경우의 수를 출력하는 문제이다.

 

풀이

일단 당연히 비트마스크 dp 문제이다.

더욱 자세한 풀이는 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648 을 참고하자.

이와 같이 각 칸에 번호를 붙이자.

solve(pos, mask) = pos 번째 위치 전까지의 번호는 모두 채워져 있고, 비트마스크가 mask 일때 경우의 수를 의미한다.

비트마스크의 표현 범위는 만약 pos 가 15라면 15~20을 표현한다. 21번부터는 표현할 필요가 없음을 알 수 있다. 왜냐하면 21번을 포함하는 타일이 1~14중 하나를 동시에 포함할 수가 없기 때문이다.

예를 들어 solve(15, 3)은 15번 칸을 채울 차례이고, 3을 이진수로 나타내면 11(2) 이기 때문에 15, 16번 칸은 이미 차 있다는 의미이다.

 

자 이제, 실제로 칸을 채우는 방법에 대해 살펴보자.

2*1 타일을 가로로 놓거나, 세로로 놓거나 2가지 방법이 가능하다.

1. 가로로 놓는 경우 : 지금 칸과 다음 칸 둘다 비어 있어야 하며, 지금 칸이 가로로 끝칸이 아니여야 한다.

2. 세로로 놓는 경우 : 지금 칸이 비었어야 하고, 밑의 칸은 무조건 비어 있으므로 된다.

 

이제 잘 됬는지 검사는 마지막 NM 번째 칸에서 mask 가 0 인지만 확인해 주면 된다.

그 이유는 NM 번째 칸에서 비트마스크의 정보는 존재하지 않는 가상의 N+1번째 줄에 대한 것이며, 이 칸에 하나라도 채워진 것이 있다면 답이 될수 없다.

 

시간복잡도 : $O(NM*2^M)$

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

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

const int MAXN = 14;
const int MOD = 9901;

int n, m;
int dp[MAXN*MAXN+10][(1<<MAXN)+10];

int solve(int pos, int mask)
{
    if(pos==n*m) return mask==0;

    int &ret=dp[pos][mask];
    if(ret!=-1) return ret;
    ret=0;

    if(mask&1)
    {
        ret+=solve(pos+1, mask>>1);
    }
    else
    {
        if(pos%m!=m-1 && (mask&2)==0) ret+=solve(pos+2, mask>>2);
        ret+=solve(pos+1, (mask>>1)|(1<<(m-1)));
    }
    ret%=MOD;
    return ret;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    memset(dp, -1, sizeof(dp));
    int i, j;

    scanf("%d%d", &n, &m);
    printf("%d", solve(0, 0));

    return 0;
}