[C/C++] 백준 - 1780번 : 종이의 개수

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

1780번: 종이의 개수

구간 내 숫자가 모두 같으면 넘어가고 만약 구간 내 숫자가 다른 게 하나라도 있다면 총 9등분한 후 등분한 부위를 다시 검사해주는 것이다. 큰 것에서 작은 것으로 넘어가기 때문에 분할 정복 알고리즘을 사용하여 해결할 수 있다.

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

using namespace std;

int N;
int board[3000][3000];
int counting[3];

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

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

void Function(int n, int y, int x) {
	if (isSame(n, y, x)) {
		counting[board[y][x]+1]++;
		return;
	}

	int Third = n / 3;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			Function(Third, y + i * Third, x + j * Third);
		}
	}
}

void Output() {
	for (int i = 0; i < 3; i++) cout << counting[i] << endl;
}

int main() {
	CUNLINK;
	Input();
	Function(N, 0, 0);
	Output();

	return 0;
}