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

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

1780번: 종이의 개수

[풀이]

분할 정복으로 풀었다.

종이의 크기가 1*1이거나 종이에 쓰여 있는 수가 모두 같을 경우 해당 수로 채워진 종이의 개수를 추가하였다.

만약 종이에 쓰여있는 수 중 다른 게 있으면 현재 종이를 9등분한 정보를 인수로 재귀함수를 호출하였다.

 

#include <iostream>
using namespace std;
#define Max 2187//3^7

int N;
int Paper[Max][Max];
int Minus = 0, Zero = 0, Plus = 0;//각각 종이의 개수

void getPaper(int startx, int starty, int curSize) {
	//종이 크기가 1이면
	if (curSize == 1) {
		if (Paper[startx][starty] == -1)Minus++;
		else if (Paper[startx][starty] == 0)Zero++;
		else if (Paper[startx][starty] == 1)Plus++;
		return;
	}

	for (int i = startx; i < startx + curSize; i++) {
		for (int j = starty; j < starty + curSize; j++) {
			//숫자 다른 게 있으면 재귀
			if (Paper[startx][starty] != Paper[i][j]) {
				for (int k = 0; k < 3; k++) {
					for (int l = 0; l < 3; l++) {
						//9등분하고 각각 종이의 첫 좌표를 인수로 재귀함수 호출
						getPaper(startx + (curSize / 3)*k, starty + (curSize / 3)*l, curSize / 3);
					}
				}
				return;
			}
		}
	}
	//숫자가 모두 같으면 해당 종이 개수 추가
	if (Paper[startx][starty] == -1)Minus++;
	else if (Paper[startx][starty] == 0)Zero++;
	else if (Paper[startx][starty] == 1)Plus++;
	return;
	
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Paper[i][j];
		}
	}
	getPaper(0, 0, N);

	cout << Minus << endl << Zero << endl << Plus << endl;
}

int main() {
	solution();
	return 0;
}