백준 1780번: 종이의 개수 (C++)

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

1780번: 종이의 개수

 

 

풀이

9개 부분으로 분할해야 하는 분할 정복 문제.

 

-1, 0, 1  -  3가지 종이가 있어서 cnt[3] 을 선언해서 각각 넣어주려고 한다.

 

partition 함수를 보면, 종이를 전부 탐색하고 가장 왼쪽 상단의 숫자와 다른 숫자가 있을 때 tmp_cnt를 체크해주었다.

tmp_cnt에 따라 전체가 같은 색이면 cnt[ paper + 1 ]의 숫자를 추가시켰다.

그리고 하나라도 다른 부분이 있을 경우 9가지 부분으로 나누어서 똑같이 반복 시켰다.

 

전체 코드

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

int N;
int paper[2200][2200] = { 0, };
int cnt[3] = { 0, };

void partition(int x, int y, int n) {
	int tmp = paper[x][y];
	int tmp_cnt = 0;

	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (tmp != paper[i][j]) {
				tmp_cnt++;
			}
		}
	}

	if (!tmp_cnt) cnt[paper[x][y] + 1]++;
	else {
		partition(x, y, n / 3);

		partition(x, y + n / 3, n / 3);
		partition(x, y + n / 3 * 2, n / 3);

		partition(x + n / 3, y, n / 3);
		partition(x + n / 3 * 2, y, n / 3);

		partition(x + n / 3, y + n / 3, n / 3);
		partition(x + n / 3 * 2, y + n / 3, n / 3);
		partition(x + n / 3, y + n / 3 * 2, n / 3);
		partition(x + n / 3 * 2, y + n / 3 * 2, n / 3);
	}
	return;

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cin >> paper[i][j];
	}

	partition(0, 0, N);

	for (int i = 0; i < 3; i++) cout << cnt[i] << '\n';
}