BOJ 14600 & 14601:: 샤워실 바닥 깔기

2018년 2월 12일

트로미노 타일링이라고 하는 아주 유명한 문제입니다. 여기서는 불가능하면 -1을 출력하라고 했는데, 사실 항상 가능합니다. 증명은 수학적 귀납법으로 합니다.

$2^n\times 2^n$ 크기의 체스판에서 어느 한 칸이 빠져도 항상 L-트로미노로 덮을 수 있다.

$n=1$인 경우는 너무나도 자명합니다. $n=k$일 때 성립한다고 가정하면 $n=k+1$일 때에는 다음과 같이 체스판을 쪼개 가운데 L-트로미노 하나를 덮고 나머지 네 곳은 $n=k$일 때 덮는 방식으로 덮으면 $n=k+1$일 때에도 항상 덮을 수 있습니다.

재귀함수를 써서 위 증명을 그대로 구현하면 됩니다.


#include<cstdio>

using namespace std;

int floor[128][128];

int pow2 (int n) {
    int ans = 1;
    for (int i = 0; i < n; i++) ans *= 2;
    return ans;
}

void tiling(int r, int c, int k, int rd, int cd, int nstart) {
    if (k == 1) {
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                if (!(i == rd && j == cd))
                    floor[r+i][c+j] = nstart;
        return;
    }

    int sh = pow2(k-1);
    int didx = 2 * (rd / sh) + cd / sh;
    int ntroq = (sh * sh - 1) / 3;

    tiling(r + sh * (rd / sh), c + sh * (cd / sh), k-1, rd % sh, cd % sh, nstart);
    for (int i = 1; i < 4; i++) {
        int idx_nxt = (didx + i) % 4;
        int nrd = idx_nxt / 2 == 0? sh-1 : 0;
        int ncd = idx_nxt % 2 == 0? sh-1 : 0;
        tiling(r + sh * (idx_nxt / 2), c + sh * (idx_nxt % 2), k-1, nrd, ncd, nstart + i*ntroq);
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            if (2*i + j != didx)
                floor[r+sh-1+i][c+sh-1+j] = nstart + 4 * ntroq;
}

int main(void) {
    int k, a, b;
    scanf("%d %d %d", &k, &a, &b);

    tiling(0, 0, k, a-1, b-1, 1);
    floor[a-1][b-1] = -1;

    int s = pow2(k);
    for (int i = s-1; i >= 0; i--) {
        for (int j = 0; j < s; j++)
            printf("%d ", floor[j][i]);
        printf("\n");
    }
    return 0;
}
PS