Baekjoon 1780번 종이의 개수

문제

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

걸린 시간

00 : 20 : 26

풀이

C++

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

int ans[3]; // -1, 0, 1
int paper[2187][2187];

void solve(int y, int x, int n){
    set<int> s;
    for(int i = y; i < n+y; i++)
        for(int j = x; j < n+x; j++)
            s.insert(paper[i][j]);
    // 기저 사례1 : 종이가 하나의 숫자로만 되어있는 경우
    if(s.size() == 1){
        ans[*s.begin()+1]++;
        return;
    }
    // 기저 사례2 : 제일 작은 종이의 단위일때 (3x3)
    if(n == 3){
        for(int i = y; i < n+y; i++)
            for(int j = x; j < n+x; j++)
                ans[paper[i][j]+1]++;
        return;
    }
    // 재귀 호출 : 9개의 종이로 자르기
    for(int i = y; i < n+y; i+=n/3)
        for(int j = x; j < n+x; j+=n/3)
            solve(i, j, n/3);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> paper[i][j];
    solve(0, 0, n);
    for(int i = 0; i < 3; i++)
        cout << ans[i] << "\n";
    return 0;
}

설명은 주석으로 충분할 것 같다.