[c++/백준] 1780 종이의 개수

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

1780번: 종이의 개수

분할정복과 재귀를 사용해서 구현할 수 있는 문제이다.

기존에 2등분으로 나누는 문제를 한번 풀어봤기 때문에 조금 수월하게 풀 수 있었다.

 

2등분으로 나눌 때는 4가지 경우의 수밖에 없지만 3등분으로 나눌 때는 9가지의 경우의 수가 있다.

 

check값은 사각형의 x,y값으로 나타냈고, check값에 들어갈 수 있는 수는 -1, 0, 1밖에 없기 때문에 만약 check값과, for문을 돌면서 나오는 map[i][j]의 값이 다르면 check값을 2로 갱신하였다. 

 

check가 2일 때 재귀문을 돌 수 있게 했고 반드시 return값이 있어야한다. 아님 값이 아예 틀림

#include <iostream>
using namespace std;

int map[2200][2200];
int n;
int mOne = 0;
int zero = 0;
int one = 0;

void division(int xStart, int yStart, int sSize) {
	int check = map[xStart][yStart];
	for (int i = xStart; i < xStart + sSize; i++) {
		for (int j = yStart; j < yStart + sSize; j++) {
			if (check != map[i][j]) {
				check = 2;
			}
			if (check == 2) {
				division(xStart, yStart + sSize / 3 + sSize / 3, sSize / 3);
				division(xStart + sSize / 3, yStart + sSize / 3 + sSize / 3, sSize / 3);
				division(xStart + sSize / 3 + sSize / 3, yStart + sSize / 3 + sSize / 3, sSize / 3);
				division(xStart, yStart + sSize / 3, sSize / 3);
				division(xStart + sSize / 3, yStart + sSize / 3, sSize / 3);
				division(xStart + sSize / 3 + sSize / 3, yStart + sSize / 3, sSize / 3);
				division(xStart, yStart, sSize / 3);
				division(xStart + sSize / 3, yStart, sSize / 3);
				division(xStart + sSize / 3 + sSize / 3, yStart, sSize / 3);
				return;
			}
		}
	}
	if (check == 0) {
		zero++;
	}
	else if (check == -1)
		mOne++;
	else
		one++;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	division(0, 0, n);
	cout << mOne << '\n';
	cout << zero << '\n';
	cout << one << '\n';
}