[1780번] 종이의 개수 - 분할정복법 [C++]

이 문제는 분할정복법으로 푸는 문제로 분할정복법이란 큰 문제를 작은 문제로 나누어 처리하는 방식(Top-down)으로

보통 재귀를 이용한 방법이 일반적이다.

이 문제를 좀 오래동안 풀었는데 그 이유는 for문에 j를 써야하는데 i라고 써서 눈이 나쁜 필자는 이걸 찾는데 일주일이 걸렸다고 한다...
이 문제와 비슷한 문제로는 쿼드트리가 있다.

#include <iostream>
 
using namespace std;
 
int output[3];  // -1 0 1
int arr[2187][2187];
 
void paper(int x, int y, int N){
    int first = arr[x][y];
    bool flag = true;
    
    for(int i = x; i < x + N; i++){
        for(int j = y; j < y + N; j++){
            if(arr[i][j] != first){
                flag = false;
                break;
            }
        }
    }
    
    if(flag) {
        output[first + 1]++;
    }
    else {
        for(int a = x; a < x + N; a += N/3 ){
            for(int b = y; b < y + N; b += N/3){
                paper(a, b, N/3);
            }
        }
    }
}
 
int main(){
    int N;
    
    cin >> N;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> arr[i][j];
        }
    }
    
    paper(0, 0, N);
    
    for(int i = 0; i < 3; i++){
        cout << output[i] << endl;
    }
    
    return 0;
}