(C++) - 백준(BOJ) 1780번 : 종이의 개수 답

www.acmicpc.net/problem/1780

1780번: 종이의 개수

9부분으로 나누어 종이의 개수를 파악할 때 반복되는 부분에 대해 재귀로 구현했습니다.

 

풀이방법 

 n = 9일 때 3*3짜리 정사각형 또는 1*1짜리 정사각형으로 종이를 나누어 볼 수 있습니다. 이럴 경우 가로를 3등분 세로를 3등 분하며 계속 종이를 세기 때문에 원래의 영역에서 9등분씩 나누어지게 됩니다. 따라서 이 9부분에 대해 종이인지 아닌지 판별한 후 종이가 아니라면 다시 현재 영역에 대해 9등분으로 나누어 재귀탐색을 진행합니다. 만약 종이라면 -1, 0, 1에 대한 답을 추가하시면 됩니다.

 

Code

#include <iostream>
using namespace std;

int n;
int paper[2200][2200];
int zeroPaper;
int minusPaper;
int onePaper;

bool isPaper(int i,int j,int width){
    int pivot = paper[i][j];
    for(int x = i; x < i + width; x++){
        for(int y = j; y < j + width; y++){
            if(pivot!=paper[x][y]){
                return 0;
            }
        }
    }
    return 1;
}

void cutPaper(int i,int j,int n){
    if(!isPaper(i,j,n)){
        //1~3행
        cutPaper(i,j,n/3);
        cutPaper(i,j+n/3,n/3);
        cutPaper(i,j+n/3*2,n/3);
        //4~6행
        cutPaper(i+n/3,j,n/3);
        cutPaper(i+n/3,j+n/3,n/3);
        cutPaper(i+n/3,j+n/3*2,n/3);
        //7~9행
        cutPaper(i+n/3*2,j,n/3);
        cutPaper(i+n/3*2,j+n/3,n/3);
        cutPaper(i+n/3*2,j+n/3*2,n/3);
    }else{
        if(paper[i][j]==0) zeroPaper++;
        else if(paper[i][j]==1) onePaper++;
        else minusPaper++;
    }
    
    return;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> paper[i][j];
    cutPaper(0,0,n);
    cout << minusPaper << '\n';
    cout << zeroPaper << '\n';
    cout << onePaper << '\n';
}