(C++) BOJ/백준 1780 - 종이의 개수

문제 출처 : BOJ 1780 - 종이의 개수 https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

내가 아주 어려워하는 분할 정복 문제이다.

N*N 크기의 행렬에서 종이가 모두 같은 수로 되어 있다면 그대로 놔두고,

다른 수가 하나라도 있으면 종이를 9개로 자르는 것을 계속 반복하는 것이다.

 

이 문제는 재귀함수만 잘 작성한다면

분할 정복 문제 중에서는 그나마 쉽게 풀 수 있는 문제 같다.

 

 

최종 코드

#include <iostream>
#include <map>
#define MAX 2188
using namespace std;

int arr[MAX][MAX];

map<int, int> ans;

int N;

void f(int x, int y, int n) {
	if (n == 1) {
		ans[arr[x][y]]++;
		return;
	}

	map<int, int> tmp;

	for (int i = x; i < x + n; i++)
		for (int j = y; j < y + n; j++)
			tmp[arr[i][j]]++;

	if (!tmp[0] && !tmp[1]) { ans[-1]++; return; }
	else if (!tmp[-1] && !tmp[1]) { ans[0]++; return; }
	else if (!tmp[-1] && !tmp[0]) { ans[1]++; return; }

	for (int i = x; i < x + n; i += n / 3)
		for (int j = y; j < y + n; j += n / 3)
			f(i, j, n / 3);
}

int main() {
	ios_base::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 >> arr[i][j];

	f(0, 0, N);

	cout << ans[-1] << '\n' << ans[0] << '\n' << ans[1] << '\n';
 
	return 0;
}