[Baekjoon/백준] 1780번: 종이의 개수(C/C++)

단계별로 풀어보기 20단계(분할 정복) 3번 문제

https://www.acmicpc.net/step/20

분할 정복 단계

---

백준 1780번: 종이의 개수

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

1780번: 종이의 개수

---

문제 설명

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력: 첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

---

접근 방법

이번 문제는 종이 크기 N을 입력받고 NxN 크기의 종이에 적힌 숫자들을 입력받아서 그 숫자들의 개수를 출력하는 문제다. 숫자는 -1, 0, 1이 있으며, 종이에 적힌 숫자는 종이를 정사각형으로 봤을때 그 숫자들로 가득차야지만 인정된다.

이 문제는 지난 번에 풀었던 같은 단계의 다른 문제들과는 달리, 3등분을 하고 N의 범위가 조금 크다. 다만 그뿐이라서 그냥 이전 문제들 풀이와 마찬가지로, 이중 배열을 사용해서 재귀 함수를 통해 이중 반복문을 돌면서 첫번째 값과 다른 값이 있다면 종이를 3등분으로 잘라버리고, 같은 값이 없다면 첫번째 값의 개수를 증가시키면 된다. 이후 그 증가한 값을 출력하기만 하면 문제를 해결할 수 있다.

---

코드

#include <iostream>
#include <string>
using namespace std;
#define MAX 2187	//3^7

int paper[MAX][MAX];
int minOne = 0, zero = 0, one = 0;

void slice(int x, int y, int N) {
	int temp = paper[x][y];

	for (int i = x; i < x + N; i++)
		for (int j = y; j < y + N; j++) {
			if (temp != paper[i][j]) {
				slice(x, y, N / 3);
				slice(x, y + N / 3, N / 3);
				slice(x, y + (N * 2) / 3, N / 3);
				
				slice(x + N / 3, y, N / 3);
				slice(x + N / 3, y + N / 3, N / 3);
				slice(x + N / 3, y + (N * 2) / 3, N / 3);
				
				slice(x + (N * 2) / 3, y, N / 3);
				slice(x + (N * 2) / 3, y + N / 3, N / 3);
				slice(x + (N * 2) / 3, y + (N * 2) / 3, N / 3);
				return;
			}
		}

	if (temp == -1)
		minOne++;
	else if (temp == 0)
		zero++;
	else if (temp == 1)
		one++;
}

int main(int argc, char *argv[]) {
	int N;
	cin >> N;

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

	slice(0, 0, N);
	cout << minOne << endl;
	cout << zero << endl;
	cout << one << endl;

	return 0;
}

---

결과

백준 제출 결과