백준 1780번 종이의 개수(c++)

 

1780번: 종이의 개수

문제 분석

문제는 N x N 행렬을 보고, 3종류(-1, 0, 1)의 종이가 각각의 개수를 구하는 문제이다.

여기서 2개의 규칙을 반복하는데, 문제의 해석을 이러하다.

1. 만약 종이가 모두 같은 수로 되어있다면 이 종이를 그대로 사용한다. 

2. 1번이 아닌 경우, 종이를 같은 크기의 종이 9개로 자르고, 각 잘린 종이에 대해 1번의 과정을 반복한다.

-> 처음 주어진 예제의 종이가 1장이고, 이것이 3개의 수(-1, 0, 1) 중 하나로 이루어져 있지 않다면 2번을 수행.
2번을 통해 9장이 된 종이 각각을 다시 1번을 통해, 1장으로 판단할지, 9장으로 자를지 판단을 반복한다.
결국 분할정복 알고리즘이 핵심이라고 할 수 있다.

입력에서 N x N에 대한 N의 입력은 '1 ≤ N ≤ 37, N은 3^k 꼴'이 조건이다. 이는 9장을 쪼갰을 때, 각 종이의 크기 N이 3^(k-1)이 되도록 하기 위함이다. 

ex) N=27일 경우, 2번을 수행하면 N=9, N=3...

---

문제 풀이

분할 정복을 사용하기로 했고, 재귀가 탈출하기 위한 base case를 작성해야 하는데, 이는 크게 2가지로 구분할 수 있다. 

base 1. 1번의 경우. 검사하는 종이 전체가 모두 같은 숫자일 때. (N의 크기 3이상일 때)

• 이 때는 종이의 숫자가 무엇인지 판단한 뒤, -1, 0, 1 중에 1장을 추가한다.
• 여담으로, 처음 문제를 해석하면서, '9 x 9 배열에서 [0][0]을 시작으로 6x6배열이 모두 '0'이라면 1장이 아닐까?' 라는 의문을 처음 품었다. 이 의문때문에 문제에 시간을 많이 소모했다. 이는 문제분석이 부족했던 의문점이었다. 문제 분석에서, 처음 1번과 2번의 과정만을 반복하기에 위의 의문점의 경우에도 똑같이 9장으로 나누게 된다. 
  즉 위의 궁금증의 경우, 6x6배열에는 0이 4장 나오게 된다.

base 2. 종이를 더이상 나누지 못하는 상태. 즉, 종이의 N의 크기가 1일 때.

• 색종이를 자르다보면 결국 더 이상 자르지 못하는 떄에 이르게 된다. 이 때는 그 종이의 숫자가 무엇인지 판단한 뒤, 해당 숫자에 대한 종이 개수를 1장 추가한다.

위의 2가지 base case가 아닐 경우, 계속 9장으로 나누면 된다!

---

c++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int N;
int c1 = 0; // -1 종이
int c2 = 0; // 0 종이
int c3 = 0; // 1 종이

void cutting(vector<vector<int>> &vec, int row, int col, int num) {
	bool flag = true;
	if (num == 1) {
		if (vec[row][col] == -1) {
			c1++;
		}
		else if (vec[row][col] == 0) {
			c2++;
		}
		else {
			c3++;
		}
		return;
	} // 종이의 크기가 1x1일 경우. 이 때 숫자가 -1, 0, 1인지 확인함.

	for (int i = row; i < row + num; i++) {
		for (int j = col; j < col + num; j++) {
			if (vec[row][col] != vec[i][j]) { // 모두 같은 숫자가 아닐 경우
				flag = false;
				break;
			}
		}
		if (!flag)
			break;
	}// 종이가 모두 같은 숫자인자 아닌지 판단함.

	if (flag == false) { // 현재의 종이가 모두 같은 숫자가 아니면
		int n = num / 3; // N의 크기를 3개로 나눈 과정.
		for (int i = row; i < row + num; i += n) {
			for (int j = col; j < col + num; j += n) {
				cutting(vec, i, j, n); // 재귀 반복.
			}
		}
	}// 9장 쪼개기
	else {// 현재의 종이가 모두 같은 숫자이면
		if (vec[row][col] == -1) {
			c1++;
		}
		else if (vec[row][col] == 0) {
			c2++;
		}
		else {
			c3++;
		}
		return;
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	vector<vector<int>> paper(N, vector<int>(N, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> paper[i][j];
		}
	}

	cutting(paper, 0, 0, N);

	cout << c1 << '\n' << c2 << '\n' << c3;

	return 0;
}

 + 여담으로, break를 2번 사용하기 싫어서 goto문을 사용했다가 문제의 정답이 한참 나오지 않았다. goto문은 코드 자체를 손상시키기 쉽기 때문에 코딩테스트를 목표로 삼는 사람이라면 최후의 경우 외에는 쓰지 않도록!

코드 리뷰는 언제나 환영입니다!