문제

• NxN 크기 종이에 -1 0 1 저장

1. 종이가 모두 같은 수로 되어있으면 종이 그대로 사용
2. 1이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해 1의 과정을 반복

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

풀이

분할정복으로 푸는 문제

#include <bits/stdc++.h>
using namespace std;
int output[3];  // -1 0 1 개수 저장
int arr[2187][2187];
 
void paper(int x, int y, int N){
    int first = arr[x][y];
    bool flag = true;
    
    for(int i = x; i < x + N; i++){
        for(int j = y; j < y + N; j++){
            if(arr[i][j] != first){
                flag = false;
                break;
            }
        }
    }
    
    if(flag) {// 다 똑같으면 개수 ++
        output[first + 1]++;
    }
    else {// 다르면 분할 
        for(int i = x; i < x + N; i += N/3 ){
            for(int j = y; j < y + N; j += N/3){
                paper(i, j, N/3); 
            }
        }
    }
}
 
int main(){
    int N;
    
    cin >> N;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> arr[i][j];
        }
    }
    
    paper(0, 0, N);
    
    for(int i = 0; i < 3; i++){
        cout << output[i] << endl;
    }
    
    return 0;
}