BOJ. 1780

#BOJ1780

종이의 개수

종이를 쪼개는 과정 자체가 아무리 봐도 분할정복을 사용하는 거 같다. 근데 분할 정복 문제를 풀다가 화병 난 적이 많아서 단계별로 처리해보기로 했다. 가장 먼저 하기로 한 것은 2187개를 행과 열로 갖고 있는 어레이에 들어오는 인풋값을 받아보기로 했다. main 함수 안에서 받을 때는 segmentation fault가 나와서 밖에서 선언을 해보았다. 지역변수에서 전역변수로 변환한 것 만으로 segmentation fault가 사라졌는데 왜 이런 일이 일어나는지부터 확인해 보고 싶었지만 접근 권한 외에는 크게 찾지 못해서 알게되면 글에 추가해 보겠다.

결국 이 문제는 재귀로 해결해야 하기 때문에 먼저 모든 수가 같은 것을 찾는 함수를 설정하였다. check 함수로 이 사각형이 하나의 종이 쪼가리가 될 수 있는지를 고민 하였다. 두 번째로 이 종이가 완전하지 않다면 종이 를 3 3 으로 나눠서 9개로 나눠야 하기 때문에 9개로 나누는 경우의수를 설정하였다. 9개의 시작점과 크기를 다시 9개로 나누면서 확인하는 함수에 넣어주면 재귀가 완성된다.

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[2188][2188], ans[3] = {0};

bool check(int r, int c, int N){
    for (int i = r; i < r + N; i++){
        for (int j = c; j < c + N; j++){
            if (arr[r][c] != arr[i][j]) return false;
        }
    }
    return true;
}

void solve(int r, int c, int N){
    if (check(r, c, N)){
        ans[arr[r][c] + 1] ++;
    }
    else{
        int temp = N / 3;
        for (int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                solve(r + temp * i, c + temp * j, temp);
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    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 << ans[i] << "\n";
    }
    
}