BOJ - 색종이 만들기(2630)

실버3 : 분할정복 문제이다.

Code

//
//  main.cpp
//  algorithm_prac
//
//  Created by 최완식 on 2021/04/05.
//
 
#include <iostream>
 
using namespace std;
const int WHITE = 0;
const int BLUE = 1;
const int ERROR = -1;
int N = 0;
int input[128][128] = {0,};
int white = 0;
int blue = 0;
 
int check(int ys, int ye, int xs, int xe, int n){
    int main_number = input[ys][xs];
    int check = main_number;
    for (int i = ys; i < ye; i++) {
        for (int j = xs; j < xe; j++) {
            if (main_number != input[i][j]) {
                check = ERROR;
                break;
            }
        }
    }
    return check;
}
 
void go(int ys, int ye, int xs, int xe, int n){
    if (n == 0) {
        return;
    }
    int state = check(ys, ye, xs, xe, n);
    if (state == WHITE) {
        white++;
    } else if (state == BLUE) {
        blue++;
    } else {
        int next = n/2;
        go(ys, ys+next, xs, xs+next, next);
        go(ys, ys+next, xs+next, xe, next);
        go(ys+next, ye, xs, xs+next, next);
        go(ys+next, ye, xs+next, xe, next);
    }
}
 
int main(){
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> input[i][j];
        }
    }
    go(0, N, 0, N, N);
    cout << white << '\n' << blue << '\n';
    
    return 0;
}
 

Reference

• 백준(2630번) - 색종이 만들기