[cpp 알고리즘] 백준 1780 종이의 개수

[백준] 1780 종이의 개수 cpp 풀이

분할정복, 재귀

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

문제 요약

예시 문제를 푼 방법

N(1 ≤ N ≤ 37, N은 3k 꼴) * N 크기의 행렬로 표현되는 종이에서, 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다.
- 만약 종이가 모두 같은 수라면, 그대로 사용한다.
- 아니라면, 종이를 같은 크기의 종이 9개로 자르고, 각각의 종이에 대해서 위의 과정을 반복한다.
출력값으로, 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하면 된다.

풀이 정리

이전에 진행한 분할정복 문제와 같다.
즉 구간을 나눠가면서, (1) N=1인지 확인하기, (2) 그 부분이 모두 같은 값으로 이루어져있는지 확인하기 (이중 for문) , (3) 아니라면 그 부분을 다시 9개의 구간으로 나눠서 이 과정을 반복한다. 
 
다만, 차이점은 (1) 4개로 구분하는 것이 아니고, 9개로 구분한다. (2) 입력을 문자열로 받는 것이 아니라 숫자 하나씩 받을 수 있다. (3) 누적 개수를 구해서 출력한다. 이 세가지로 볼 수 있다. 

C++ 코드

#include <iostream>
using namespace std;

int N; //3^7=2187
int arr[2200][2200];
int ans[3]; //-1, 0, 1;

void divide(int y, int x, int n) {
    //cout << y << x << " " << n <<"\n";
    if (n==1) {
        ans[arr[y][x]+1]++;
        return;
    }
    
    bool MINUSONE = true;
    bool ZERO = true;
    bool PLUSONE = true;
    for(int i=y; i<y+n; i++) {
        for(int j=x; j<x+n; j++) {
            if(arr[i][j] == 0){
                MINUSONE = false;
                PLUSONE = false;
            }
            else if(arr[i][j] == -1) {
                ZERO = false;
                PLUSONE = false;
            }
            else if(arr[i][j] == 1) {
                ZERO = false;
                MINUSONE = false;
            }
        }
    }

    if(MINUSONE) ans[0]++;
    else if(ZERO) ans[1]++;
    else if(PLUSONE) ans[2]++;
    else{
        divide(y, x, n/3);
        divide(y, x+(n/3), n/3);
        divide(y, x+(n/3)*2, n/3);
        divide(y+(n/3), x, n/3);
        divide(y+(n/3), x+(n/3), n/3);
        divide(y+(n/3), x+(n/3)*2, n/3);
        divide(y+(n/3)*2, x, n/3);
        divide(y+(n/3)*2, x+(n/3), n/3);
        divide(y+(n/3)*2, x+(n/3)*2, n/3);
    }
}

int main(){
    cin >> N;
    for(int y=0; y<N; y++){
        for(int x=0; x<N; x++)
            cin >> arr[y][x];
    }
    
    divide(0,0,N);
    
    for(int i=0; i<3; i++)
        cout << ans[i] << "\n";
    return 0;
}