[분할 정복] BOJ 2630 색종이 만들기

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

2630번: 색종이 만들기

 

문제 해결 알고리즘

 

큰 정사각형부터 분할정복 해가면서 전부 다 비어있으면 잘라진 정사각형에, 다 채워져있으면 파란색 정사각형에 +1을 해주고 만약 둘 다 아닐 경우 4분할해서 또 거기서 분할정복을 해준다.

 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int cnt_1 = 0, cnt_0 = 0;
int arr[129][129];

void div_conq(int x, int y, int N){

  int temp = 0;

  for(int i=x;i<x+N;i++){
    for(int j=y;j<y+N;j++){
      if(arr[i][j]) temp++;
    }
  }

  if(!temp) cnt_0++;
  else if(temp == N*N) cnt_1++;
  else {
    div_conq(x+N/2, y+N/2, N/2);
    div_conq(x, y+N/2, N/2);
    div_conq(x+N/2, y, N/2);
    div_conq(x, y, N/2);
  }


}

int main(){
  int N; cin >> N;

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cin >> arr[i][j];
    }
  }

  div_conq(0, 0, N);

  cout << cnt_0 << '\n' << cnt_1;
}