백준 1780. 종이의 개수 [실패]

1.실패 원인

분할 정복은 늘 약했다. 재귀는 사실 아직도 제대로 이해가 안된다. 그래서 dp 부분에서도 무조건 bottom up 방식을 사용했었고.. 이번 문제는 충격 그 자체였다. 일단 문제가 이해가 안됐고, 어떻게 무슨 방식으로 풀어야하는지 도저히 감을 못잡았다. 꾸준함님의 풀이를 보고나서 감탄을 금치 못했다. 경이로운 수준.. 감은 잡았다지만 문제가 어떻게 나오냐에 크게 휘둘릴 것 같다.

 

2.작성 코드

#include <iostream>
using namespace std;

int A[2187][2187];
int result[3];
void func(int y, int x, int n) {
	if (n == 1) {
		result[A[y][x] + 1]++;
		return;
	}

	bool minus = true;
	bool zero = true;
	bool plus = true;

	for (int i = y; i < y + n; i++)
		for (int j = x; j < x + n; j++)
		{
			if (A[i][j] == -1) {
				zero = false;
				plus = false;
			}
			else if (A[i][j] == 0) {
				minus = false;
				plus = false;
			}
			else if (A[i][j] == 1) {
				zero = false;
				minus = false;
			}
		}

	if (minus == true) {
		result[0]++;
	}
	else if (zero) {
		result[1]++;
	}
	else if (plus) {
		result[2]++;
	}
	else {
		int div = n / 3;
		func(y, x, div);
		func(y, x + div, div);
		func(y, x + 2 * div, div);

		func(y + div, x, div);
		func(y + div, x + div, div);
		func(y + div, x + 2 * div, div);

		func(y + 2 * div, x, div);
		func(y + 2 * div, x + div, div);
		func(y + 2 * div, x + 2 * div, div);
	}
	return;
}

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> A[i][j];

	func(0, 0, N);

	for (int i = 0; i < 3; i++)
		cout << result[i] << endl;
}

3.참고 코드

https://jaimemin.tistory.com/1075

백준 1780번 종이의 개수

4. 해결 방안

처음에 분할정복을 그냥 잠시 킵 할까 생각했다. 코테에서 과연 나올까 고민이 됐었는데, 알고리즘 기초에 포함되어 있길래 다시 공부를 시작했다. 문제를 많이 풀어보는 것 밖에는 답이 없을 것 같다.