백준 2630번: 색종이 만들기

 

 

 

 

 

분할 정복 문제다.

재귀(순환 호출)를 통해 분할 정복을 반복한다.

 

 

 

 

 

중요포인트

1. '하얀 색종이' 이거나 '파란 색종이' 이려면 한변의 길이가 N일때 1이나 0의 갯수가 넓이(N*N)와 같아야 한다.
2. 1번을 충족하지 않을 시, 재귀(순환 호출)을 통해 분할 정복을 한다.
3. 분할 정복 시, 변을 2등분 시키므로 항상 4등분된 사각형이 나온다.
4. 3번의 4개 사각형에 대해 재귀(순환 호출을) 한다.
5. 4번을 할 때, 각 사각형의 시작점(x, y)과 한변의 길이만 정해주면 된다.

 

 

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

int map[129][129];	// 2의 7승이 최대라서 +1한거
int white, blue;

void div_conq(int y, int x, int n) {
	int cnt_white = 0;
	int cnt_blue = 0;
	for (int i = y; i < y + n; i++) {
		for (int j = x; j < x + n; j++) {
			if (map[i][j] == 0)
				cnt_white++;
			else
				cnt_blue++;
		}
	}

	//전부 흰색일때
	if (cnt_white == n * n)
		white++;

	//전부 파란색일때
	else if (cnt_blue == n * n)
		blue++;

	else {
		div_conq(y, x, n / 2);	//왼쪽 위 사각형
		div_conq(y, x + n / 2, n / 2);	//오른쪽 위 사각형
		div_conq(y + n / 2, x, n / 2);	//왼쪽 아래 사각형
		div_conq(y + n / 2, x + n / 2, n / 2);	//오른쪽 아래 사각형
	}
}

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 << white << "\n";
	cout << blue << "\n";
	return 0;
}