BOJ 1780 종이의 개수

www.acmicpc.net/problem/1780

1780번: 종이의 개수

마찬가지로 분할 정복 문제이다.

쿼드 트리 문제와 비슷한데 분할해야 하는 구간만 늘었을 뿐이다.

#include <iostream>
#include <vector>
using namespace std;

int mi, ze, pl;
vector<vector<int>> ar;

void f(int x, int y, int n) {
	int tmp = ar[x][y];
	int mod = n / 3;
	int mod2 = mod * 2;
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (tmp != ar[i][j]) {
				f(x, y, mod);
				f(x, y + mod, mod);
				f(x, y + mod2, mod);

				f(x + mod, y, mod);
				f(x + mod, y + mod, mod);
				f(x + mod, y + mod2, mod);

				f(x + mod2, y, mod);
				f(x + mod2, y + mod, mod);
				f(x + mod2, y + mod2, mod);
				return;
			}
		}
	}
	if (tmp == -1) mi++;
	else if (tmp == 0) ze++;
	else pl++;
}

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

	int n;
	cin >> n;
	ar.resize(n, vector<int>(n));

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

	f(0, 0, n);
	
	cout << mi << endl;
	cout << ze << endl;
	cout << pl << endl;

	return 0;
}

각각에 대해서 

1 2 3

4 5 6

7 8 9

라고 할때

f(x, y, mod);
f(x, y + mod, mod);
f(x, y + mod2, mod);

f(x + mod, y, mod);
f(x + mod, y + mod, mod);
f(x + mod, y + mod2, mod);

f(x + mod2, y, mod);
f(x + mod2, y + mod, mod);
f(x + mod2, y + mod2, mod);

이렇게 접근해주면 된다.