[Silver 2] 1780 종이의 개수

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

 

종이를 자를 때는 같은 크기의 종이를 9등분 한다.

이는 분할 정복을 사용하여 문제를 해결해야 함을 알 수 있다.

 

종이를 자를 때 N = 9인 경우 크기 3인 종이가 9개 존재하게된다.

따라서 원래 종이의 크기가 n인 경우 다음 종이는 n/3이 된다는 것을 알 수 있다.

 

종이를 자를지 선택할 때는 paper[y][x]의 값이 paper[y부터 y + size][x부터 x + size 값] 에 있는 값이 다를 경우 자른다.

 

자르지 않는 경우 paper[y][x]에 존재하는 값을 count하면 된다.

 

#include <iostream>
using namespace std;

int N;
int paper[2200][2200];
int onePaper = 0;
int zeroPaper = 0;
int minousPaper = 0;

void FindPaper(int y, int x, int n){
    bool same = true;

    for(int  i = y;i<y+n;i++){
        for(int j = x;j<x+n;j++){
            if(paper[i][j] != paper[y][x]){
                same = false;
                break;
            }
        }
        if(!same)
            break;
    }


    if(same){
        if(paper[y][x] == 0)
            zeroPaper++;
        else if(paper[y][x] == 1)
            onePaper++;
        else
            minousPaper++;
    }
    else{
        FindPaper(y, x, n/3);
        FindPaper(y + n / 3, x, n/3);
        FindPaper(y + n / 3 + n / 3, x, n/3);
        FindPaper(y, x + n / 3, n/3);
        FindPaper(y, x + n / 3 + n / 3, n/3);
        FindPaper(y + n / 3, x + n / 3, n/3);
        FindPaper(y + n / 3, x + n / 3 + n / 3, n/3);
        FindPaper(y + n / 3 + n / 3, x + n / 3, n/3);
        FindPaper(y + n / 3 + n / 3, x + n / 3 + n / 3, n/3);
    }
}

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>>paper[i][j];
    }
    FindPaper(0, 0, N);

    cout<<minousPaper<<'\n';
    cout<<zeroPaper<<'\n';
    cout<<onePaper<<'\n';

}