[Silver 2] 2630 색종이 만들기

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

 

문제에서 NxN크기의 종이를 NxN, N/2xN/2, ... 크기 순서로 자르라고 나타나있다.

따라서 0, 0 자리부터 탐색을 시작하고, NxN크기부터 자를 수 있는지 판단한다.

 

판단의 기준은 0번째 자리부터 N번째 자리까지 탐색을 진행한 후

처음 색과 진행과정 중 발견한 색이 다를 경우 자른다.

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int N;
int arr[129][129];
int white = 0;
int blue = 0;
void dfs(int y, int x, int cnt){
    bool cut = false;

    int color = arr[y][x];

    for(int i = y;i<y + cnt; i++){
        for(int j = x; j<x + cnt; j++){
            if(arr[i][j] != color){
                cut = true;
                break;
            }
        }
    }
    if(cut){
        dfs(y, x, cnt/2);
        dfs(y, x + cnt / 2, cnt/2);
        dfs(y + cnt / 2, x, cnt/ 2);
        dfs(y + cnt / 2, x + cnt / 2, cnt / 2);
    }
    else{
        if(color == 1)
            blue++;
        else
            white++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>N;
    
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++)
            cin>>arr[i][j];
    }

    dfs(0, 0, N);

    cout<<white<<'\n';
    cout<<blue<<'\n';
}