BOJ 1780 종이의 개수

문제 링크 : https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

요약

-1, 0, 1로 이루어진 N x N의 행렬이 있을 때  전체 영역이 모두 같은 값이라면 한 장만 사용해도 되고,

그게 아니라면 가로 3, 세로 3 영역으로 9등분하여 각 영역이 모두 같은 값으로 이루어질 때까지 나누었을 때 -1, 0, 1로만 채워진 종이의 각각의 개수를 구하는 문제.

 

풀이

전형적인 분할정복 문제!! 부분 행렬의 전부를 탐색했을 때 모두 같은 값이라면 한 장만 사용하도록 기저를 잡고 그게 아니라면 재귀 함수를 이용해서 9등분하여 조건에 해당하는지 확인하고 각 영역의 답을 모두 합병해준다.

 

코드

#include<iostream>
using namespace std;
int n, arr[2200][2200];
int ans[3];
void sol(int d, int r, int cnt) {
	int num = arr[d][r];
	int chk = -1;
	for (int i = d; i < d + cnt; i++) {
		for (int j = r; j < r + cnt; j++) {
			if (num != arr[i][j]) {
				chk = 1;
			}
		}
	}
	if (chk == -1) {
		ans[num + 1]++;
		return;
	}
	int div = cnt / 3;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			sol(d + div * i, r + div * j, div);
		}
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	sol(0, 0, n);
	for (int i = 0; i < 3; i++)
		cout << ans[i]<<"\n";
}