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

 

 

풀이

3x3으로 분할해야하는 조금 귀찮은 분할정복 문제이다.

#include <iostream>

using namespace std;

int countA = 0, countB = 0, countC = 0;
int paper[2188][2188];

void conquer(int y, int x, int size) {
	int num = paper[y][x];

	for (int i = y; i < y + size; i++) {
		for (int j = x; j < x + size; j++) {
			if (num != paper[i][j]) {
				conquer(y, x, size / 3);
				conquer(y + size / 3, x, size / 3);
				conquer(y + size * 2 / 3, x, size / 3);
				conquer(y, x + size / 3, size / 3);
				conquer(y + size / 3, x + size / 3, size / 3);
				conquer(y + size * 2 / 3, x + size / 3, size / 3);
				conquer(y, x + size * 2 / 3, size / 3);
				conquer(y + size / 3, x + size * 2 / 3, size / 3);
				conquer(y + size * 2 / 3, x + size * 2 / 3, size / 3);

				return;
			}
		}
	}

	if (num == -1) countA++;
	else if (num == 0) countB++;
	else countC++;

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

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

	conquer(0, 0, n);

	cout << countA << '\n' << countB << '\n' << countC;

	return 0;
}