(C++) - 백준(BOJ) 2630번 : 색종이 만들기 답

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

재귀를 이용해 푸는 문제였습니다.

 

풀이방법 

 면적이 다른 색인 색종이가 나오면 2로 계속 나누고 면적이 같다면 파란색인지 흰색인지 판별하여 답을 구하는 문제였습니다.

 

Code

#include <iostream>
using namespace std;
int paper[130][130];
int n;
int whiteNum;
int blueNum;
bool isSameColor(int i, int j, int width){
    int color = paper[i][j];
    for(int x = i; x < i + width; x++)
        for(int y = j; y < j + width; y++)
            if(paper[x][y]!=color)
                return 0;
    return 1;
}

void cutPaper(int i,int j,int n){
    if(!isSameColor(i,j,n)){
        cutPaper(i+n/2,j+n/2,n/2);
        cutPaper(i,j+n/2,n/2);
        cutPaper(i+n/2,j,n/2);
        cutPaper(i,j,n/2);
    }else{
        if(paper[i][j]==0)
            whiteNum+=1;
        else
            blueNum+=1;
    }
    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 << whiteNum << '\n' << blueNum << '\n';
}