(2630) 색종이 만들기

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

단계별로 풀어보기

24단계(분할 정복) 1번째

 

 

 

분할 정복 알고리즘을 간단하게 설명하면, 어떤 문제를 더이상 분할할 수 없을때까지 분할하고, 가장 하위 단계의 문제를 해결한 뒤, 역방향으로 다시 조합해 원래 문제의 최적해를 찾는 방법이다. 재귀와 같이 쓰이는 경우가 많다.

 

어담으로 어떤 색종이의 부분이 단색인지 확인하는 방법은 누적합을 이용했다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, w= 0, b= 0;
  
  cin >> n;
  
  vector v(n+1, vector<int> (n+1));
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin >> v[i][j];
      v[i][j]+= v[i-1][j]+v[i][j-1]-v[i-1][j-1];
    }
  }
  
  auto func= [&](auto self, int x, int y, int l) -> void {
    int acc= v[x+l-1][y+l-1]-v[x-1][y+l-1]-v[x+l-1][y-1]+v[x-1][y-1];
    
    if(acc==0){
      w++;
      return;
    }else if(acc==l*l){
      b++;
      return;
    }
    
    self(self, x, y, l/2);
    self(self, x, y+l/2, l/2);
    self(self, x+l/2, y, l/2);
    self(self, x+l/2, y+l/2, l/2);
  };
  
  func(func, 1, 1, n);
  
  cout << w << "\n" << b;
  
  return 0;
}