[Jungol] 정올 2543 타일 채우기

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1804&sca=40

Approach

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

2 × 2 타일에서 하나의 타일에 홀이 있다면 타일을 채우는 방법은 항상 존재.

마찬가지로, 4 × 4 타일에서 하나의 타일에 홀이 있다면 타일을 채우는 방법은 항상 존재

 

2k × 2k 타일 에서 하나의 타일에 홀이 있다면 타일을 채우는 방법은 항상 존재

 

 

2k × 2k  타일을 4등분하는 일을 재귀적으로 반복하는데 홀이 속한 구역을 기준으로

4등분한 중심에 기본 타일 4가지 중에 한 타일을 채워갑니다. (분할 정복)

▶ void tiling(int sr, int sc, int len, int hr, int hc)

▶ void tiling(구간 시작r, 구간 시작c, 구간 크기, 구간내 배수구의 위치)

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 1024;
int N, arr[LM][LM];
int hr, hc;
 
void tiling(int sr, int sc, int len, int hr, int hc) {
    if (len == 1) return;
    int hnum = 1, hf = len / 2;
    int mr = sr + hf - 1, mc = sc + hf - 1;
 
    if (hr > mr) hnum += 2;
    if (hc > mc) hnum += 1;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            int nsr = sr + hf * i, nsc = sc + hf * j;
            if (i * 2 + j + 1 == hnum) {
                tiling(nsr, nsc, hf, hr, hc);
            }
            else {
                arr[mr + i][mc + j] = hnum;
                tiling(nsr, nsc, hf, mr + i, mc + j);
            }
        }
    }
}
 
void output() {
    int i, j;
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            printf("%d ", arr[i][j]);
        }
        puts("");
    }
}
 
int main() {
    scanf("%d %d %d", &N, &hr, &hc);
    tiling(0, 0, N, hr, hc);
    output();
    return 0;
}