[백준] 2630 색종이 만들기

해당 문제는 주어진 그래프에서 파란색 종이와 하얀색 종이의 개수를 구하는 문제이다.

 

예시로 주어진 그래프를 보다보면 패턴이 보이는데 

<그림 5> 처럼 숫자가 다른경우 계속 쪼개지면서 종이가 나누어 지게 된다.

따라서 재귀함수를 이용해서 개수를 구하면 된다.

<그림 2> 처럼 N을 먼저 탐색해보고 숫자가 다른게 하나라도 있다면 반으로 줄이는 방식으로 문제를 해결하면 된다.

 

 

 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input2630(130,vector<int>(130,0));
int blueCount2630 = 0;
int whiteCount2630 = 0;

void divide2630(int N, int x, int y){
    
    if(N==1){
        if(input2630[x][y] == 1)
            blueCount2630++;
        if(input2630[x][y] == 0)
            whiteCount2630++;
        return;
    }
    
    bool checkBlue = true;
    bool checkWhite = true;
    for(int i=x;i<x+N;i++){
        for(int j=y;j<y+N;j++){
            if(input2630[i][j] != 1)
                checkBlue = false;
            if(input2630[i][j] != 0)
                checkWhite = false;
        }
    }
    
    if(checkBlue){
        blueCount2630++;
        return;
    }
    if(checkWhite){
        whiteCount2630++;
        return;
    }
    
    divide2630(N/2, x, y);
    divide2630(N/2, x+(N/2), y);
    divide2630(N/2, x, y+(N/2));
    divide2630(N/2, x+(N/2), y+(N/2));
}

void paper2630(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin>>N;
    
    for(int i=1;i<=N;i++){
        for(int j=1; j<=N; j++){
            int a; cin>>a;
            input2630[i][j] = a;
        }
    }
    
    divide2630(N, 1, 1);
    
    cout<<whiteCount2630<<"\n";
    cout<<blueCount2630<<"\n";
    
}

 

 

□ 유용한 반례

4
0 0 0 0
1 1 1 1
1 1 1 1
1 1 1 1

ANS: 4,6