취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14601번 문제인 샤워실 바닥 깔기 (Large)이다.
문제는 아래 링크를 확인하자.

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

타일을 알맞게 배치하는 방법은 항상 존재한다. 다음은 그 귀납적 증명이다.

i) k=1인 경우 ㄱ자 타일을 항상 배치할 수 있다는 것은 자명하다.

ii) k=p일 때 타일을 항상 배치할 수 있다고 가정하자. 이 때, k=p+1일 때 타일을 항상 배치할 수 있음을 보이면 문제를 해결할 수 있다.

한 변의 길이가 2^(p+1)인 바닥을 한 변의 길이가 2^p인 사각형 넷으로 나눠보자. 이 때, "배수구"가 있는 영역이 단 한 칸 존재한다. k=p인 케이스는 항상 타일을 배치할 수 있으므로, "배수구"가 있는 영역을 ㄱ자 타일을 이용해 채우는 것은 가능하다. 또한, 나머지 세 영역에 한 칸씩 걸치게끔 ㄱ자 타일을 하나 배치할 수 있다는 점을 관찰하자. 이와 같이 타일을 놓은 뒤 각 영역에 생긴 타일이 놓인 한 칸을 "배수구"취급하여 남은 영역들에 타일을 놓을 경우 한 변의 길이가 2^p이고 한 칸이 배수구인 바닥을 채우듯 ㄱ자 타일을 채울 수 있다는 것을 알 수 있다. 

위의 증명에서 보여주는 재귀적인 방법을 구현하여 문제를 해결하자.

입력으로 주어지는 좌표가 행과 열 순이 아닌 가로좌표와 세로좌표 순임에 유의하자. 또한, 좌하단의 좌표가 (1,1), 우상단의 좌표가 (2^k,2^k)임에도 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int K;
int ans[128][128];
int num = 1;

void func(int N, int offR, int offC, int R, int C) {
	if (N > 1) {
		if (R < N / 2 && C < N / 2) {
			ans[offR + N / 2][offC + N / 2] = ans[offR + N / 2 - 1][offC + N / 2] = ans[offR + N / 2][offC + N / 2 - 1] = num++;
			func(N / 2, offR, offC, R, C);
			func(N / 2, offR + N / 2, offC, 0, N / 2 - 1);
			func(N / 2, offR, offC + N / 2, N / 2 - 1, 0);
			func(N / 2, offR + N / 2, offC + N / 2, 0, 0);
		}
		else if (R < N / 2 && C >= N / 2) {
			ans[offR + N / 2][offC + N / 2] = ans[offR + N / 2 - 1][offC + N / 2 - 1] = ans[offR + N / 2][offC + N / 2 - 1] = num++;
			func(N / 2, offR, offC, N / 2 - 1, N / 2 - 1);
			func(N / 2, offR + N / 2, offC, 0, N / 2 - 1);
			func(N / 2, offR, offC + N / 2, R, C - N / 2);
			func(N / 2, offR + N / 2, offC + N / 2, 0, 0);
		}
		else if (R >= N / 2 && C < N / 2) {
			ans[offR + N / 2][offC + N / 2] = ans[offR + N / 2 - 1][offC + N / 2 - 1] = ans[offR + N / 2 - 1][offC + N / 2] = num++;
			func(N / 2, offR, offC, N / 2 - 1, N / 2 - 1);
			func(N / 2, offR + N / 2, offC, R - N / 2, C);
			func(N / 2, offR, offC + N / 2, N / 2 - 1, 0);
			func(N / 2, offR + N / 2, offC + N / 2, 0, 0);
		}
		else {
			ans[offR + N / 2][offC + N / 2 - 1] = ans[offR + N / 2 - 1][offC + N / 2 - 1] = ans[offR + N / 2 - 1][offC + N / 2] = num++;
			func(N / 2, offR, offC, N / 2 - 1, N / 2 - 1);
			func(N / 2, offR + N / 2, offC, 0, N / 2 - 1);
			func(N / 2, offR, offC + N / 2, N / 2 - 1, 0);
			func(N / 2, offR + N / 2, offC + N / 2, R - N / 2, C - N / 2);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K;
	int R, C; cin >> C >> R; R--, C--;
	func(1 << K, 0, 0, R, C);

	for (int r = (1 << K) - 1; r > -1; r--) {
		for (int c = 0; c < (1 << K); c++) {
			if (ans[r][c]) cout << ans[r][c] << ' ';
			else cout << -1 << ' ';
		}
		cout << '\n';
	}
}