[boj 14601] 샤워실 바닥 깔기

태그 : 분할정복

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

14601번: 샤워실 바닥 깔기 (Large)

처음에는 k의 크기가 large문제임에도 7인걸로 보아서 3개를 깔을수있는 완전탐색 분기를 어떻게하면 효율적으로 짤까 생각했었다. 완탐이 아직 부족한가보다 하고 이 문제를 쳐보니까

이산수학, 그 중에서도 수학적 귀납법 으로 증명할 수 있는 트로미노 타일링이라는 유명한 문제였고, 이 문제에서 요구하는 타일을 전부 칠하는 과정 또한 이 귀납법을 이용해서 풀 수 있다.

 

증명참고:http://www.aistudy.com/math/induction_johnsonbaugh.htm

 

 

(증명) n*n(단 n은 2의제곱꼴)에서 타일을 하나 제거한 불완전 보드(한칸만 비어있는 보드) 는 전부 트로미노로 채울 수 있다.

1) k= 1(기본단계)

ㅇㅇ(빈공간을 의미하는 노란색을 어디두더라도 채우는게 가능하다는 뜻 ㅎ)

2) 귀납단계

i)2^k*2^k승 불완전보드(한칸만 비어있는 보드!)를 트로미노로 전부 채울 수 있다고 가정하자.

이때 우리는

ii) 2^(k+1)*2^(k+1)승 보드를 마찬가지로 전부 채울 수 있다는 것을 보이면 된다.

 

 

위 그림에서의 노란부분, 즉 2^k, 2^k부분은 이미 채울 수 있다고 가정하였기 떄문에, 신경 쓸 필요가 없다.

2^(k+1)*2^(k+1) 타일에서 (2^k*2^k)부분이 아닌 나머지 부분들의 가운대부분을 타일로 칠해버리면?( ==뚫어버리면?)

 

2^(k+1)*2^(k+1)에서의 기존부분을 제외한 나머지 3개의 부분도 전부 불완전 보드가 된다!

 

이제, 이 귀납단계에서의 풀이를 문제를 푸는데 적용해보자.

 

1)  우리가 채워야할 전체 타일을 4부분(4사분면)으로 나누고

2)  지금 불완전 타일이 아닌 부분, 즉 뚫려있는 부분이 없는 부분을 제외한 나머지 부분들의 [가운대 부분]을 한칸씩 뚫어준다.

이떄, 뚫려있는 부분이 있는지 없는지는 2중 for문으로 전체구간을 돌면서 확인 할 수 있다.

3) 이를 재귀적으로 구간을 좁히면서 반복한다.

(같은 과정을 구간을 다르게 하면서 반복한다?? 분할정복이다!)

Colored by Color Scripter

cs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e9;
typedef pair<int, int> pi;
int k, x, y;
int dp[256][256];// 타일이 칠해진 배열
int clk = 0;// 칠할 타일의 넘버
bool isin(int x, int y, int siz) {//정해진 구간에서 칠해진(혹은 뚫린)타일이 있으면  0을 리턴
    for (int i = x; i < x + siz; i++) {
        for (int j = y; j < y + siz; j++) {
            if (dp[i][j] != 0)return 0;
        }
    }
    return 1;
}
void rec(int x, int y, int siz) {
        ++clk;
        // 4구간으로 나눈뒤에 이 구간내에 칠해진 타일이 없는경우(즉, 아직 불완전타일)이 아니면, 그 부분들의 가운데를 칠해준다.
        if (isin(x, y, siz >> 1))dp[x + (siz >> 1) - 1][y + (siz >> 1) - 1] = clk;
        if (isin(x, y + (siz >> 1), siz >> 1))dp[x + (siz >> 1) - 1][y + (siz >> 1)] = clk;
        if (isin(x + (siz >> 1), y, siz >> 1))dp[x + (siz >> 1)][y + (siz >> 1) - 1] = clk;
        if (isin(x + (siz >> 1), y + (siz >> 1), siz >> 1))dp[x + (siz >> 1)][y + (siz >> 1)] = clk;
        // 재귀적으로 이 과정을 반복한다.    
        if (siz == 2)return;
    
        rec(x, y, siz >> 1);
        rec(x + (siz >> 1), y, siz >> 1);
        rec(x, y + (siz >> 1), siz >> 1);
        rec(x + (siz >> 1), y + (siz >> 1), siz >> 1);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> k >> x >> y;
    dp[y - 1][x - 1] = -1;
    rec(0, 0, 1 << k);
    for (int i = (1 << k) - 1; i >= 0; i--) {
        for (int j = 0; j < (1 << k); j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
}

 

 

느낀점)  귀납법으로 타일을 채울 수 있다??를 증명만하면 타일을 어떤식으로 배치할지는 바로 알 수 있었다.

이산수학을 다시 공부할 필요성을 느꼇다;;