백준 02630 - 색종이 만들기

출처 : https://www.acmicpc.net/problem/2630 

2630번: 색종이 만들기

 

고려사항

- 분할정복 기법 사용.

- 통일되지 않은 n * n 색종이라면 시작점을 구분지어 n / 2 크기로 분할 후 재검사 ( 25 - 29 라인 )

- color 값을 넘겨 주어 일치여부 판별

- n == 1 일때, 조사중인 색상과 다르다면, 25 - 29 라인 진입 않고, return 0

 

#include <iostream>
using namespace std;

int divide(int y, int x, int n, int paper[][129], int color){
    bool isComplete = true;
    int cnt = 0;

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

    if(isComplete){
        return 1;
    }

    if(n == 1){
        return 0;
    }

    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            cnt += divide((y + n * i / 2), (x + n * j / 2), n / 2, paper, color);;
        }
    }

    return cnt;
}

int main() {
    int n, blue, white;
    int paper[129][129];

    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>paper[i][j];
        }
    }

    white = divide(1, 1, n, paper, 0);
    blue = divide(1, 1, n, paper, 1);

    cout<<white<<"\n"<<blue;
    return 0;
}