색종이 만들기 (feat. 백준, 2630번)

색종이 만들기
https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int white, blue, arr[128][128];
void solution(int x, int y, int n) {
	register int sum = 0;
	for (register int i = 0, j; i < n; ++i)
		for (j = 0; j < n; ++j)
			sum += arr[x + i][y + j];
	if (sum == n * n)
		++blue;
	else if (sum == 0)
		++white;
	else
		solution(x, y, n / 2), solution(x + n / 2, y, n / 2), solution(x, y + n / 2, n / 2), solution(x + n / 2, y + n / 2, n / 2);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	white = blue = 0;
	register int N;
	cin >> N;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j)
			cin >> arr[i][j];
	solution(0, 0, N);
	cout << white << "\n" << blue;
	return 0;
}
// *&)*@*

문제의 요구사항처럼 색종이의 모든 칸이 같은 색이 아닌 경우, 재귀함수를 다시 호출하면서 N을 반으로 나누는 형태입니다.