BOJ 백준 1648번 격자판 채우기

 

 

BOJ 백준 1648 격자판 채우기

 

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

1648번: 격자판 채우기

 

N × M 크기의 격자판을 2 × 1 또는 1 × 2 크기의 도미노로 채우는 방법의 수를 구해야 한다.

 

2 × M 크기의 격자판을 채우는 문제(BOJ 11726번)를 이전에 푼 적이 있어서 이와 유사한 문제라고 생각하고 접근했다. 그러나 해결 방법을 고민하면서 이전 것과는 전혀 다른 문제임을 알았다.

 

 

 

처음에는 이전 문제처럼 왼쪽 열에서부터 오른쪽 열로 차례대로 채워가는 방법을 고민했다. 그러면 Dynamic Programming을 통해 아래처럼 메모이제이션 배열을 정의할 수 있을 것이다.

 

d[i][j]: 첫 번째 열부터 i - 1번째 열까지 꽉 채운 상태에서 i번째 열의 상태가 j인 경우에 채울 수 있는 방법의 수

 

하지만 격자판의 행의 수가 주어지는 입력에 따라 정해져서 상태 j를 정의하기 어렵다. 아무리 입력으로 주어지는 행의 최댓값이 14라고 해도 모든 입력마다 상태 j를 정의하는 건 쉽지 않은 일이다.

 

 

 

그러면 이전 문제 풀이법과는 관점을 달리 볼 필요가 있다. 매번 값이 달라지는 행의 수를 N을 고려하여 위쪽 행에서 아래쪽 행으로, 왼쪽 열에서부터 오른쪽 열로 차례대로 채우는 방법도 가능할 것이다. 그런데 이 때 각 행의 데이터는 어떻게 저장해야 하는지 의문점이 생긴다. i - 1번째 행까지 모두 채워져 있다고 가정하더라도 현재 보고 있는 i번째 행의 상태가 답의 결정 요인이 될 텐데, i번째 행의 상태가 될 수 있는 경우의 수는 최소 2^M이다. (i번째 행에 있는 모든 각 칸이 채운 상태인지 비어 있는 상태인지 그 경우의 수만 고려했을 때 말이다.) 게다가 그렇게 채워진 행의 상태에 도미노를 어떻게 배치하는지에 따라 채울 수 있는 경우의 수는 더 늘어날 수 있다. 즉, 매번 행마다 상태를 고려하여 격자판을 채우는 방법의 수를 구하는 건 비효율적이다. 또 한 번의 관점 전환이 요구된다.

 

 

d[i][j]: i번째 칸을 보고 있는 상태에서 i번째 칸부터 i + M - 1번째 칸까지 M개 칸의 상태가 j일 때, 남아 있는 빈 칸을 채우는 방법의 수

(단, 처음부터 i - 1번째 칸까지는 모두 찬 상태이고, i + M번째 칸부터는 비어 있음이 보장됨)

 

 

격자판에 있는 모든 칸이 위에서부터 아래로, 그리고 왼쪽에서부터 오른쪽으로 0부터 N * M - 1까지 번호가 지정되어 있다고 가정하자. i - 1번째 칸까지 모두 채워져 있으면서 i번째 칸부터 M개의 칸의 상태가 j이고 나머지 빈칸을 도미노를 채운다고 할 때, i번째 칸에 2 × 1 크기의 도미노를 배치하면 i ~ i + 1번째 칸이, 1 × 2 크기의 도미노를 배치하면 i번째와 i + M번째 칸이 채워진다. 단, 도미노가 차지하게 되는 칸은 빈칸이어야 한다. 참고로 상태 j를 다룰 때 Bit Masking(비트마스킹)을 이용한다. M개의 각 비트가 1이면 채워진 상태, 0이면 빈 상태임을 의미한다. 이를 정리하면 다음과 같다.

 

 

go(idx, status): idx ~ idx + M - 1번째 칸의 상태가 status이고 idx번째 칸을 채우려고 할 때, 남은 빈칸을 채울 수 있는 방법의 수를 반환하는 재귀 함수

위에서 정의한 재귀 함수의 base case: idx가 N * M일 때, status가 0이면 1을, status가 1이면 0을 반환함

 

 

1) idx번째 칸이 이미 채워져 있는 경우

→ go(idx + 1, status >> 1)로 이동

 

 

2) idx번째 칸이 빈 칸인 경우

 

(1) 2 × 1 크기 도미노로 채우는 경우

→ 맨 마지막 열이 아니여야 하고 idx + 1번째 칸이 비어있어야 함 → 조건 만족 시 idx와 idx + 1번째 칸 채워짐

→ go(idx + 2, status >> 2)로 이동

 

(2) 1 × 2 크기 도미노로 채우는 경우

→ idx와 idx + M번째 칸 채워짐

→ go(idx + 1, status >> 1 & 1 << (m - 1))로 이동

 

 

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;


const int N_MAX = 14;
const int M_MAX = 14;
const int MOD = 9901;


int n, m;
int dp[N_MAX * M_MAX][(1 << M_MAX) - 1];


int go(int idx, int status){
    if (idx >= n * m){
        if (idx == n * m && status == 0)
            return 1;
        return 0;
    }
    
    int& ret = dp[idx][status];
    if (ret != -1)
        return ret;
    ret = 0;
    
    // 이미 idx번 째 칸이 채워져 있는 경우
    if (status & (1 << 0)){
        ret += go(idx + 1, status >> 1);
    }
    // idx번 째 칸을 채워야 하는 경우
    else {
        // idx번 째 칸에 2 X 1 도미노를 채우는 경우
        // 현재 행에서 맨 마지막 열에 위치한 칸이면 2 X 1 도미노 채우지 못 함
        // idx + 1번 째 칸이 비어 있는지 확인해야 함
        if (idx % m < (m - 1) && (status & (1 << 1)) == 0){
            ret += go(idx + 2, status >> 2);
        }
        // idx번 째 칸에 1 X 2 도미노를 채우는 경우
        // 어차피 i번 째 바로 밑에 있는 칸은 비어 있을 수밖에 없음
        ret += go(idx + 1, (status >> 1) | (1 << (m - 1)));
    }
    ret %= MOD;
    return ret;
}


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