백준 1780번: 종이의 개수

 

 

 

 

 

 

분할 정복을 사용하는 문제다.

재귀(순환 호출)을 통해 분할 정복을 계속해서 해 나가면 된다.

 

비슷한데 좀더 쉬운 문제를 푼적이 있다.

 

https://gimmesome.tistory.com/59

백준 2630번: 색종이 만들기

위 문제는 변을 2분할하는 문제였고 체크해야하는 수도 0과 1 두가지였다.

이문제는 변을 3분할하고 체크해양하는 수는 -1, 0, 1 총 세가지다.

 

 

중요포인트

1. 변을 3분할 하므로 재귀도 3*3번 일어나야한다. 
2. -1, 0, 1 세가지 숫자의 갯수를 따로 세면된다. (-1을 int minus라고 하면 안된다....)

 

 

 

#include <iostream>
#include <cstring> //memset
using namespace std;

int map[2188][2188];	// 2의 7승이 최대라서 +1한거
int zero, one, minu;

void div_conq(int y, int x, int n) {
	int cnt_zero = 0;
	int cnt_one = 0;
	int cnt_minu = 0;
	for (int i = y; i < y + n; i++) {
		for (int j = x; j < x + n; j++) {
			if (map[i][j] == 0)
				cnt_zero++;
			else if (map[i][j] == 1)
				cnt_one++;
			else if (map[i][j] == -1)
				cnt_minu++;
		}
	}

	//전부 0일 때
	if (cnt_zero == n * n)
		zero++;

	//전부 1일 때
	else if (cnt_one == n * n)
		one++;

	//전부 -1일 때
	else if (cnt_minu == n * n)
		minu++;

	else {
		// 왼쪽에서 오른쪽
		//위에서 아래
		div_conq(y, x, n / 3);	
		div_conq(y, x + n / 3, n / 3);	
		div_conq(y, x + 2 * n / 3, n / 3);	
		div_conq(y + n / 3, x, n / 3);
		div_conq(y + n / 3, x + n / 3, n / 3);
		div_conq(y + n / 3, x + 2 * n / 3, n / 3);
		div_conq(y + 2 * n / 3, x, n / 3);
		div_conq(y + 2 * n / 3, x + n / 3, n / 3);
		div_conq(y + 2 * n / 3, x + 2 * n / 3, n / 3);
		
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int n;
	cin >> n;

	memset(map, 0, sizeof(map));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	div_conq(0, 0, n);	//맨처음 사각형은 시작점이 (0,0), 크기는 n


	cout << minu << "\n";
	cout << zero << "\n";
	cout << one << "\n";
	
	return 0;
}