[PS 백준 - 4.6] 14600번: 샤워실 바닥 깔기 (Small)

문제 정보

백준 14600번 - 바로가기

• 난이도: 골드 5
• 알고리즘: 분할 정복

---

코멘트

"샤워실 바닥 깔기" 문제는 Large 문제와 Small 문제로 나뉘어져 있다. Large 문제는 바닥의 크기가 128까지 늘어나지만 Small 문제는 2, 4인 경우밖에 없다. Large처럼 분할 정복 방식을 이용해서 풀면 정말 어려운 문제였을 것 같은데, Small은 조건이 문제를 너무 쉽게 만들어줘서 그냥 노가다로 출력만 해주면 된다.

그래도 나는 그 마저도 조금 생각을 하고 풀려고 직선의 방정식을 세워 문제를 풀었다. 바닥의 크기가 2일 때는 생각할 필요조차 없이 풀면 되고, 4일 때 "ㄱ" 타일의 배치를 조금 생각해야 한다. 그럼 아래와 같은 결과가 나온다.

if (i >= j + 2) { arr[i][j] = 4; continue; }
else if (i <= 3 - j) { arr[i][j] = 1; continue; }
else if (i <= j - 2) { arr[i][j] = 2; continue; }
else if (i >= 7 - j) { arr[i][j] = 3; continue; }
else arr[i][j] = 5;

---

소스 코드

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;

	int x, y;
	cin >> x >> y; // 하수구 위치

	if (n == 1) {
		for (int i = 2; i >= 1; i--) { // 층은 맨 위부터 차례대로 내려옴
			for (int j = 1; j <= 2; j++) { // 열은 왼쪽부터 그대로
				if (i != y || j != x) cout << "1 ";
				else cout << "-1 ";
				
			}
			if (i == 1) cout << "\b";
			else cout << "\n";
		}
	}


	if (n == 2) {
		int arr[5][5]; // 4층 * 4열 (0층, 0열은 무시)
		for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { arr[i][j] = 0; } }
		

		// 먼저 맵 만들기 (그래프 그리고 좌표별로 직선 함수 세워서 씀)
		for (int i = 4; i >= 1; i--) {
			for (int j = 1; j <= 4; j++) {
				if (i >= j + 2) { arr[i][j] = 4; continue; }
				if (i <= 3 - j) { arr[i][j] = 1; continue; }
				if (i <= j - 2) { arr[i][j] = 2; continue; }
				if (i >= 7 - j) { arr[i][j] = 3; continue; }
				arr[i][j] = 5;
			}
		}

		arr[y][x] = -1;

		if (y >= x + 2) { arr[3][2] = 4; }
		if (y <= 3 - x) { arr[2][2] = 1; }
		if (y <= x - 2) { arr[2][3] = 2; }
		if (y >= 7 - x) { arr[3][3] = 3; }

		for (int i = 4; i >= 1; i--) {
			for (int j = 1; j <= 4; j++) {
				if (i != y || j != x)  cout << arr[i][j] << " ";
				else cout << arr[i][j] << " ";

			}
			if (i == 1) cout << "\b";
			else cout << "\n";
		}
	}
}