[BOJ 1780] 종이의 개수

1) 문제 링크

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

2) 접근

이것도 분할 정복… 다만 base case를 많이 고민했다. kks277님 포스팅 보고 모든 원소가 같은 사례를 base case로 잡아도 $O(NlogN)$에 N이 2천 얼마 하는 수가 최대라 가능함을 깨닫고 바로 짰다.

3) 풀이

#include <iostream>
using namespace std;

int N, arr[2187][2187];
int sol[3]; // -1, 0, 1 종이 개수

int isSame(int sy, int sx, int ey, int ex, int cr){ // 같을 시 종류+1, 다를 시 -1 return
    for(int i=sy; i<=ey; ++i){
        for(int j=sx; j<=ex; ++j){
            if(cr != arr[i][j]) { return -1; }
        }
    }
    return cr+1;
}

void solve(int y, int x, int level){
    if(level > 1){ // base case: 전부 동일
        int kind = isSame(y, x, y+level-1, x+level-1, arr[y][x]);
        if(kind != -1) {
            ++sol[kind];
            return;
        }
    }
    else{ // base case: 1X1 행렬
        ++sol[arr[y][x]+1];
        return;
    }

    for(int i=0; i<3; ++i){
        for(int j=0; j<3; ++j){
            solve(y+i*level/3, x+j*level/3, level/3);
        }
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

    solve(0, 0, N);
    for(int i=0; i<3; ++i){ cout << sol[i] << endl; }

    return 0;
}

리소스 되게 많이 잡아먹는 거 같아서 놀랐는데, 입출력으로 시간 줄인 몇몇 분들 제외하면 다른 분들과 별 차이가 없었다. 이게 최적해인 듯.

4) 피드백

나중에 할 거 있으면 추가할 예정.