[C++] 2630 : 색종이 만들기

실버 Ⅲ

 

#include <iostream>

int arr[128][128] = { 0, };
int N;
int blue = 0;
int white = 0;

void df(int x, int y, int n) {

	int half = n / 2;
	
	int cnt = 0;
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (arr[i][j]) cnt++;
		}
	}

	if (cnt == 0) {
		white++;
	}
	else if (cnt == n * n) {
		blue++;
	}
	else {
		df(x, y, half);
		df(x + half, y, half);
		df(x, y + half, half);
		df(x + half, y + half, half);
		return;
	}

}

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

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

	df(0, 0, N);
	printf("%d\n%d", white, blue);
}

 

분할 정복

문제 - 1 페이지

 

분할 정복 문제..

 

네모의 왼쪽 끝 지점도 지정해 줘야 하므로

(아니면 그냥 1/4의 크기로 줄어들고 시작 지점은 0,0인 네모만 탐색..)

df(divide function)에 x, y도 건네줌..