[백준] 2630 색종이 만들기

문제 :

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

2630번: 색종이 만들기

 

풀이 :

다음과 같이 색종이가 있을때 정사각형 크기로 나눠 색종이가 모두 파란면을 또는 하얀면을 띄게 하는 작은 정사각형 색종이로 만들고 만들어진 흰 색종이 개수, 파란 색종이 개수를 출력하는 문제다. 

즉 분할 정복을 통해 탑다운 방식으로 나눠진 색종이가 조건에 맞는 색종이인지 검사하면 된다. 색종이 크기가 1x1일때까지 반복하므로 재귀를 통해 해결할수 있었다.

 

 

c++ 코드 :

//
//  colorPaper.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/02/24.
//

#include <iostream>
#include <string.h>

using namespace std;
int map[129][129];
int N;
int w = 0, b = 0;

void make_count(int x, int y, int len){
    int temp = 0;
    for(int i = x; i < x + len; i++){
        for(int j = y; j < y + len; j++){
            if(map[i][j]) { temp++; }
        }
    }
    if (!temp) { // 전체 다 흰색
        w++;
    }else if(temp == len * len) { // 전체 다 블루
        b++;
    }else {
        make_count(x, y, len / 2);
        make_count(x + len/2, y, len / 2);
        make_count(x, y + len/2 , len / 2);
        make_count(x + len/2, y + len/2 , len / 2);
    }
    return;
}

int main(){
    cin >> N;
    memset(map, 0, sizeof(map));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >>map[i][j];
        }
    }
    
    make_count(0, 0, N);
    cout << w << '\n';
    cout << b << '\n';
    return 0;
}