(1992) 쿼드트리

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

단계별로 풀어보기

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

 

 

 

색종이 만들기와 같은 방식으로 풀면 된다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector v(n+1, vector<int> (n+1));
  
  for(int i=1;i<=n;i++){
    string s;
    
    cin >> s;
    
    for(int j=1;j<=n;j++){
      v[i][j]= s[j-1]-'0';
      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) -> string {
    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)  return "0";
    else if(acc==l*l)  return "1";
    
    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)+
      ")";
  };
  
  cout << func(func, 1, 1, n);
  
  return 0;
}