[C++] 백준 1780 : 종이의 개수

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

1780번: 종이의 개수

 

 

divide and conquer

 

 

비슷한 문제:https://www.acmicpc.net/problem/1074

1074번: Z

/2냐 /3이냐의 차이만 있음

 

 

어.. 음...

분할정복은 기본적으로 재귀함수를 많이 사용하니까

재귀함수에서 return 조건을 잘 확인해 주는 게 중요할 것 같다

기본적인 문제라 더 할말이 없네..

#include <iostream>
using namespace std;

int map[2187][2187];
int zero_cnt, one_cnt, minus_cnt;
int didj[9][2] = {
	{0, 0}, {0, 1}, {0, 2},
	{1, 0}, {1, 1}, {1, 2},
	{2, 0}, {2, 1}, {2, 2}
};

void dq(int si, int sj, int len) {
	if (len < 0) return;

	int start = map[si][sj];
	bool divide = false;
	for (int i = si; i < si + len; i++) {
		if (divide) break;
		for (int j = sj; j < sj + len; j++) {
			if (map[i][j] != start) {
				divide = true;
				break;
			}
		}
	}

	if (divide) {
		int nl = len / 3;
		for (int k = 0; k < 9; k++) {
			dq(si + nl * didj[k][0], sj + nl * didj[k][1], nl);
		}
	}
	else {
		if (start == 0) zero_cnt++;
		else if (start == 1) one_cnt++;
		else minus_cnt++;
	}
}

int main() {
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		for(int j = 0; j<N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	dq(0, 0, N);
	printf("%d\n%d\n%d", minus_cnt, zero_cnt, one_cnt);
}