[BOJ] 백준 1074 Z

문제링크 : https://www.acmicpc.net/problem/1074

이 문제는 원하는 답을 찾아 범위를 나누며 재귀한다는 점에서 분할정복에 속하는 문제 같다.

이전 문제인 쿼드트리(https://gpfatp.blogspot.com/2019/07/boj-1992.html)와 같이
4범위 전부 재귀를 돌면, 최대 범위는 2^15 * 2^15이기 때문에 시간초과가 걸린다.
(쿼드트리문제에선 최대 2^6 * 2^6 이었다.)

따라서 4범위 전부 재귀를 실시하는게 아닌, 목표값인 R과 C가 속한 범위에만 재귀를 실시해야 한다.

소스코드 :

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



int cnt = 0;
vector<int> arr;
unsigned int n,r, c;
void Z(int x1, int x2, int y1, int y2) {
 

 if (y1 == r && x1 == c) {
  unsigned int var = n;
  for (int i = 0; i < arr.size(); i++) {
   var /= 2;
   int tmp = var * var;
   switch ((arr[i]))
   {
   case 0:
    cnt = cnt + tmp * 0;
    break;
   case 1:
    cnt = cnt + tmp * 1;
    break;
   case 2:
    cnt = cnt + tmp * 2;
    break;
   case 3:
    cnt = cnt + tmp * 3;
    break;
   default:
    break;
   }
  }
  cout << cnt;
  return;
 }

 else {

  if ((y1+y2)/2 > r) {
   if ((x1 + x2) / 2 > c) {
    arr.push_back(0);
   
    Z(x1, ((x1 + x2) / 2), y1, ((y1 + y2) / 2));
   }
   else {
    arr.push_back(1);
  
    Z(((x1 + x2) / 2), x2, y1, ((y1 + y2) / 2));
   }
  }
  else if((y1 + y2) / 2 <= r) {
   if ((x1 + x2) / 2 > c) {
    
    arr.push_back(2);
    Z(x1, ((x1 + x2) / 2), ((y1 + y2) / 2), y2);
   }
   else {
    
    arr.push_back(3);
    Z(((x1 + x2) / 2), x2, ((y1 + y2) / 2), y2);
   }
  }
  
  
  
  
 }

}

int main() {


 cin >> n>>r>>c;

 unsigned int nn = 1;
 for (int i = 0; i < n; i++) {
  nn *= 2;
 }
 
 n = nn;
 Z(0, nn, 0, nn);
 
}