백준 1780. 종이의 개수 [C++]

문제 : 종이의 개수

유형 : 분할 정복

문제 해석

• 1 ≤ N ≤ 37 , N은 3k 꼴이다.

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

해결 전략

• N은 항상 3k 꼴이므로 항상 위의 그림처럼 구역을 나눌 수 있다. > 9개 구역
  • 구역 사이즈의 크기가 1이 될 때까지 y 시작 좌표, x 시작 좌표, 구역 사이즈를 구분해서 분할한다.

설계, 구현

• 37은 2187이므로 배열의 크기를 2187로 초기화 시켰다.

• 각각의 -1, 0, 1 종이의 개수가 필요하므로 answers[3] 배열로 한 번에 관리한다.

• 분할을 진행한다.
  • 각 구역의 시작 좌표를 기준으로 구역 사이즈만큼 돌면서 모두 같은 수 인지 판별한다.
    • 각 구역에서 종이가 모두 -1인 경우
    • 각 구역에서 종이가 모두 0인 경우
    • 각 구역에서 종이가 모두 1인 경우
    • 위의 3가지 경우가 아니라면, 각 구역의 종이를 같은 크기의 종이 9개로 자른다.

코드

#include <bits/stdc++.h>
using namespace std;

void solve(int sy, int sx, int size);

int N;
int paper[2187][2187];
int answers[3];

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

void solve(int sy, int sx, int size) {
	if(size < 1) return;

	int minus_cnt = 0;
	int zero_cnt = 0;
	int plus_cnt = 0;
	
	for (int i = sy; i < sy + size; i++) {
		for (int j = sx; j < sx + size; j++) {
			if (paper[i][j] == -1) minus_cnt += 1;
			else if (paper[i][j] == 0) zero_cnt += 1;
			else if (paper[i][j] == 1) plus_cnt += 1;
		}
	}
	
	if (minus_cnt == size * size) answers[0] += 1;
	else if (zero_cnt == size * size) answers[1] += 1;
	else if (plus_cnt == size * size) answers[2] += 1;	
	else {
		size = size / 3;
		for (int i = 0; i < 3; i++) {
			solve(sy, sx + size * i, size); // a b c
			solve(sy + size, sx + size * i, size); // d e f
			solve(sy + size * 2, sx + size * i, size); // g h i
		}
	}
}

void getAnswer() {
	for (int answer : answers) {
		cout << answer << endl;	
	}
}

int main() {
	init();
	solve(0, 0, N);
	getAnswer();

	return 0;
}