취미로 코딩하기

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

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

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

14601번 문제(링크)에서 입력의 크기가 작아진 문제이다. 해당 글을 참고하여 문제를 해결하자.

위와 같은 풀이를 사용하지 않아도, 가능한 입력의 종류가 상당히 적으므로(20가지) 모든 상황의 답을 미리 입력해두는 것으로도 문제를 해결할 수 있다.

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

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

#include <iostream>
using namespace std;

int K;
int ans[4][4];
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';
	}
}