[백준] 2630번 색종이 만들기 C++ 코드

코드

#include <iostream>

using namespace std;

int n, a[130][130], white, blue;

// 길이만큼 전부 체크
// 만약에 해당 부분이 색종이로 채워지지 않으면
// 4등분해서 확인 (좌상 우상 좌하 우하)

bool check(int x, int y, int len, int num) {
	for(int i = 0; i < len; i++) {
		for(int j = 0; j < len; j++) {
			if(a[i + x][j + y] != num) return false;
		}
	}
	return true;
}

void go(int x, int y, int len) {
	// 0은 흰색
	if(check(x, y, len, 0)) {
		white++;
		return;
	}
    // 1은 파란색
	if(check(x, y, len, 1)) {
		blue++;
		return;
	}
	int halflen = len / 2;
	go(x, y, halflen);
	go(x + halflen, y, halflen);
	go(x, y + halflen, halflen);
	go(x + halflen, y + halflen, halflen);
	return;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	go(0, 0, n);
	cout << white << '\n' << blue << '\n';
	return 0;
}

풀이

종이는 모두 2^x의 길이를 가지고 있다. 주어지는 n도 2,4,8,16,32,64,128 중 하나이며 분할정복으로 쉽게 해결할 수 있다.

 

go 함수를 처음 실행하면 전체 길이를 검사한다. 만약 종이 크기가 맞다면 색종이 개수를 증가시키고 종료한다. 그게 아니라면 길이를 반으로 나눠 4등분하여 각각을 탐색한다. 이를 길이가 1이 될 때까지 반복하면 색종이 몇 개로 구성되어 있는지 확인할 수 있게 된다.