[백준] 6569번 몬드리안의 꿈

문제

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

풀이

큰 직사각형의 상태를 0(빈 칸), 1(채운 칸) 으로 경우의 수를 계산해나갔습니다.

현재칸이 blockNum 일 때 너비 w만큼의 칸을 상태를 저장해놓고 상태에 따라 가능한 직사각형을 채운다고 생각하시면 됩니다.

예를 들어, 높이가 3 너비가 5이면 직사각형의 번호는 아래와 같습니다.

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14

0번째 칸에 높이 1, 너비 2 인 직사각형을 놓을 경우면 상태를 00011(10진수 3) 으로 표현하다고 생각하시면 됩니다.

소스코드

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 11;

long long gCache[(MAX_N+1) * (MAX_N+1)][1<<MAX_N];

bool isEnd(int num,int col){

    return num%(col-1) == 0;
}

bool isEmptyOfRight(int status){

    return (status & 2) == 0;
}

bool isNotRightEnd(int blockNum, int col){

    return blockNum%col)!=(col-1);
}

long long getCntWays(int row, int col, int blockNum, int status){

    // 다 채워져 있으면 경우의 수 증가
    if(blockNum == row * col && status == 0) return 1;

    if(blockNum >= row * col) return 0; // 두 칸 증가하는 경우를 위해

    if(gCache[blockNum][status] >= 0) return gCache[blockNum][status];

    long long &ret = gCache[blockNum][status];
    ret = 0;

    // 현재 칸에 블록을 배치할 수 없는 경우
    if(status & 1){

        ret = getCntWays(row, col, blockNum+1, (status >> 1));
    }
    else{         
        // 2*1 블럭 배치하는 경우 : 현재칸이 비어있으면 무조건 가능
        ret = getCntWays(row, col, blockNum+1, (status >> 1)|(1 << (col-1)) );

        // 1*2 블럭 배치하는 경우
        // 맨 오른쪽칸 제외, 오른쪽 칸이 비어있으면 가능
        if((isNotRightEnd(blockNum,col) && isEmptyRight(status)) 
            ret += getCntWays(row, col, blockNum+2, (status >> 2)); // 현재칸이 비어있는 경우에는 1x2, 2x1 블럭 채우는 경우의 수를 더해준다

    }

    return ret;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;

    while(true){

        cin >> n >> m;

        if(n == 0 && m == 0) break;

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

        cout << getCntWays(n,m,0,0) <<"\n";
    }

    return 0;
}