백준 1780번 종이의 개수 풀이

[문제 링크]

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

[입출력 예]

입력	출력
9 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 -1 0 1 -1 0 1 -1 0 -1 1 0 1 -1 0 1 -1 0 1 -1 1 0 -1 0 1 -1	10 12 11

[소스코드]

#include <bits/stdc++.h>
#define endl '\n';
using namespace std;

int arr[2187][2187];
int cnt[3]; //0번째 : -1 개수, 1번째: 0 개수 , 2번째: 1 개수

bool checkArr(int r1, int r2, int c1, int c2){
    for ( int i = r1 ; i < r2 ; i++){
        for (int j= c1; j <c2; j++ ){
            if (arr[i][j]!=arr[r1][c1]) return false;
        }
    }
    return true;
}

void func(int r1, int r2, int c1, int c2){
    // 모두 같을 경우
     if (checkArr(r1,r2,c1,c2)){
        cnt[arr[r1][c1]+1]++;
        return;
    }

    // 조금씩 다른 숫자 9개일 경우
    if ( r2-r1 ==3 && c2 - c1 ==3 ){
        for (int i= r1; i<r2; i++){
            for (int j=c1; j<c2; j++){
                cnt[arr[i][j]+1]++;
            }
        }
        return;
    }

    int p = (r2-r1)/3;

    func(r1, r1+p, c1, c1+p);
    func(r1+p, r1+2*p, c1, c1+p);
    func(r1+2*p, r2, c1, c1+p);
    func(r1, r1+p, c1+p, c1+p*2);
    func(r1+p, r1+2*p, c1+p, c1+p*2);
    func(r1+2*p, r2, c1+p, c1+p*2);
    func(r1, r1+p, c1+p*2, c2);
    func(r1+p, r1+2*p, c1+p*2, c2);
    func(r1+2*p, r2, c1+p*2, c2);

    return;

}

int main(){
    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];
        }
    }

    func(0,n,0,n);

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


    return 0;
}