[BOJ] 1780 : 종이의 개수 (C++) with 분할 정복

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

1780번: 종이의 개수

걸린 시간 : 13분 10초

---

기본적인 분할 정복 문제이다.

분할 정복 문제는 어떤 알고리즘인지 알아차리기는 너무 쉽다. 분할정복은 누가 봐도 분할 정복이다.

(어려운 분할 정복 문제들은 분할 정복만 쓰인 게 아니고 다른 알고리즘까지 쓰인 것 같다... 세그먼트 트리 같은)

 

키 포인트는 일반항 설정이다. 기본적으로 재귀함수를 통해 base case까지 모두 커버할 수 있는 함수를 만들어야 하고, 거기에 필요한 파라미터 설정이 중요하다.

 

1. 이 문제에선 3^n 크기로 흩어져있는 사각형들을 어떻게 특정할 것인가 만 생각하면 끝이었다. 따라서 시작점의 i좌표, 시작점의 j좌표, 사각형의 크기 3개의 파라미터로 사각형을 특정해 함수를 만들었다.
2. 그 후 사각형이 모두 같은 숫자인지 검사하는 check 함수가 필요해 사용했다. 검사가 true이면 종이를 하나 카운팅하고, false이면 9개로 쪼개어 다시 재귀호출한다.
3. 이제 check 함수를 구현했다. 처음부터 필요한 모든 함수를 염두에 두고 막무가내로 구현하지 않고, 일단 필요한 함수를 먼저 사용한 후 나중에 구현하는 게 좋은 것 같다. check 함수 구현은 어렵지 않다. 코드를 참고하자.

#include <bits/stdc++.h>
using namespace std;

int arr[2188][2188];
int num[3];

bool check (int si, int sj, int n) {
	int base = arr[si][sj];
	for (int i = si; i < si+n; i++) {
		for (int j = sj; j < sj+n; j++) {
			if (base != arr[i][j])
				return false;
		}
	}
	return true;
}

void solution (int si, int sj, int n) {
	if (n == 1) {
		num[arr[si][sj]+1]++;
		return;
	}
	if (check(si, sj, n)) {
		num[arr[si][sj]+1]++;
	} 
	else {
		solution(si, sj, n/3);
		solution(si, sj+n/3, n/3);
		solution(si, sj+2*n/3, n/3);
		solution(si+n/3, sj, n/3);
		solution(si+n/3, sj+n/3, n/3);
		solution(si+n/3, sj+2*n/3, n/3);
		solution(si+2*n/3, sj, n/3);
		solution(si+2*n/3, sj+n/3, n/3);
		solution(si+2*n/3, sj+2*n/3, n/3);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	solution(0, 0, N);
	for (int i = 0; i < 3; i++) {
		cout << num[i] << "\n";
	}
	return 0;
}