BOJ 1780번 종이의 개수

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

github : https://github.com/junho0956/Algorithm/blob/master/1780/1780/%EC%86%8C%EC%8A%A4.cpp

 

그냥 반복문으로 전체를 훑어도 되지만

문제의 분류가 분할정복이여서 요구하는대로 구현하였다.

 

#include <iostream>
using namespace std;
 
int N;
int arr[2187][2187]; // 3^7
int counter[3]; // -1 0 1
 
void paper_count(int n, int y, int x) {
    bool test = true;
    for (int i = y; i < y+n; i++) {
        for (int k = x; k < x+n; k++) {
            if (arr[i][k] != arr[y][x]) {
                test = false;
                break;
            }
        }
        if (!test) break;
    }
 
    if (test) {
        if (arr[y][x] == -1) counter[2]++;
        else counter[arr[y][x]]++;
    }
    else {
        int div = n / 3;
        for (int i = 0; i < 3; i++) {
            for (int k = 0; k < 3; k++) {
                paper_count(div, y + i * div, x + k * div);
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            cin >> arr[i][k];
        }
    }
 
    paper_count(N, 0, 0);
    cout << counter[2] << '\n' << counter[0] << '\n' << counter[1];
 
    return 0;
}