#1780번 종이의 개수 (C++)

링크 : www.acmicpc.net/problem/1780

1780번: 종이의 개수

#2630번 색종이 만들기 (C++)과 유사한 문제다.

다만 범위를 어떻게 축소해나가는지가 관건이다. 

 

문제 풀이는 다음과 같다.

1. 재귀를 통해 1번째 배열부터 마지막번호까지 재귀함수를 진행한다.

2. 만약 지정된 범위의 타일을 모두 세었을 때, -1,0,1 중 한가지로만 도배되었을 경우에 

해당 값에 대한 변수를 증가시킨다. 

3. 그렇지 않을 경우에 아래와 같이 네 분할로 나누어 다시 재귀를 진행한다.

4. 이때 재귀를 진행하는 구역은 다음과 같이 9등분이 된다.

N의 범위가 9일 경우, 위의 시작지점들에서 재귀 진행 

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

int n = 0, ans_zero = 0, ans_one = 0, ans_mone = 0, arr[2200][2200];

void check(int starty, int startx, int area) {
	int zero = 0, one = 0, mone = 0;
	for (int i = starty; i < starty+area; i++) {
		for (int j = startx; j < startx+area; j++) {
			if (arr[i][j] == 1) one++;
			else if (arr[i][j] == 0) zero++;
			else mone++;
		}
	}
	if (one == 0 && mone == 0) ans_zero++; //0으로 도배됨
	else if (zero == 0 && mone == 0) ans_one++; //1로 도배됨
	else if (zero == 0 && one == 0) ans_mone++; //-1로 도배됨
	else {
		for (int i = starty; i < starty + area; i = i + (area / 3)) {
			for (int j = startx; j < startx + area; j = j + (area / 3)) check(i, j, area / 3);
		}
	}
}

int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	check(0, 0, n);
	cout << ans_mone << "\n" << ans_zero << "\n" << ans_one << "\n";
	return 0;
}

위는 2차원 배열선언, 아래는 2차원 벡터 선언

#2630번 색종이 만들기 (C++)와 #1992번 쿼드트리 (C++)의 경우, 

4등분으로 진행되기 때문에 시작지점과 끝 지점을 설정하고 4개의 재귀함수들을 선언해주었다.

 

이번 문제도 9개의 재귀함수들을 노가다로 하나하나 선언해줄수도 있지만, 

보다 넓은 범위의 문제에서 대응하고자 공식을 하나 세워 재귀를 진행했다.