[C/C++] 백준 - 2630번 : 색종이 만들기

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

분할정복의 가장 기본적인 문제로 색종이의 영역이 모두 같은 수인지 확인해주고 같은 수가 아니라면 분할만 해주면 되는 간단한 문제이다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 100000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
int answer[2];
const int MAX = 128;
int board[MAX + 1][MAX + 1];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
		}
	}
}

bool isSame(int y, int x, int size) {
	for (int i = y; i <= y + size - 1; i++) {
		for (int j = x; j <= x + size - 1; j++) {
			if (board[y][x] != board[i][j]) return false;
		}
	}
	return true;
}

void divideConquer(int y, int x, int size) {
	if (isSame(y, x, size)) {
		answer[board[y][x]]++;
		return;
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			divideConquer(y + size / 2 * i, x + size / 2 * j, size/2);
		}
	}
}

int main() {
	fastio;
	input();
	divideConquer(1, 1, N);
	cout << answer[0] << endl << answer[1] << endl;
	
	return 0;
}