이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 84 번째 글 입니다.
목차
실버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;
}