백준 1648번 격자판 채우기

문제 링크입니다: https://www.acmicpc.net/problem/1648

현재 확인하는 칸이 앞으로 확인할 칸들 중 좌측상단에 있다고 가정하고 풀어야하는 문제였습니다.

백준님의 슬라이드쉐어(https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648)를 참고하여 풀었고 이런 풀이를 생각해본 적이 없어서 놀라웠습니다.

알고리즘은 아래와 같습니다.

1. 좌측상단부터 우측하단까지 순서대로 칸마다 숫자를 부여합니다.

2. board번째 칸부터 M개의 칸들을 비트마스킹을 이용하여 확인합니다.

i) 해당 칸이 칠해져있다면 다음 칸을 좌측상단으로 기준으로 하고 확인합니다.

ii) 해당 칸이 칠해져있지 않다면 2*1 격자를 채워줍니다.

a) 만약 오른쪽에도 배치할 수 있다면 1*2 격자 또한 채워줍니다.

3. 2번의 재귀호출이 끝났을 때 마지막 칸까지 다 확인했고 모든 칸이 채워졌다면 조건을 만족했으므로 결과에 1을 더해줍니다.

#include <iostream>

#include <cstring>

using namespace std;

 

const int MAX = 14;

const int MOD = 9901;

 

int N, M;

int cache[MAX*MAX][1 << MAX];

 

int tiling(int board, int bit)

{

        //전부 채워졌다면

        if (board == N * M && bit == 0)

                 return 1;

        //기저 사례

        if (board >= N * M)

                 return 0;

       

        int &result = cache[board][bit];

        if (result != -1)

                 return result;

 

        result = 0;

        //해당 칸이 칠해져있다면 옆 칸을 확인

        if (bit & 1)

                 result = tiling(board + 1, (bit >> 1));

        else

        {

                 //해당 칸은 현재 위치에서 항상 좌상단이라고 가정하고 푼다

                 //2 * 1

                 result = tiling(board + 1, (bit >> 1) | (1 << (M - 1)));

                 //1 * 2

                 //M - 1번째 타일에 위치하지 않았고(이럴 경우 1 * 2를 놓을 수 없습니다.) 다음칸도 비어있을 경우

                 if ((board % M) != (M - 1) && (bit & 2) == 0)

                         result += tiling(board + 2, bit >> 2);

        }

        return result %= MOD;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        memset(cache, -1, sizeof(cache));

        cout << tiling(0, 0) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~