[C++] 백준 1074번 Z

 

 

2^n으로 이루어진 사각형에서 (x, y) 위치에 몇번째에 도착하는지 묻는 문제입니다.

순서는 위의 그림과 같이 Z모양으로 움직입니다.

Z라는 모양을 작은 것에서 점점 크게 그리는 반복작업이 있기때문에 분할정복 기법을 사용했습니다.

 

재귀함수를 통해서 x, y가 찾는 위치의 값과 같아질때까지 반복을 합니다.

길이가 더 이상 분할할수 없으면 +1을 해줍니다.

탐색 중인 사분면에 찾는 위치가 있을 수 없으면 그 사분면의 크기만큼 +를 해줍니다.

 

#include <iostream>
#include <math.h>
using namespace std;

int n, r, c;
int result;

void recursion(int x, int y, int len) {
   if (y == r && x == c) {         //찾는 좌표의 결과값 출력
      cout << result << endl;
      return;
   }
   if (len == 1) {               // +1
      result++; return;
   }
   if (!(y <= r && r<y + len && x <= c && c<x + len)) { //
      result += len * len;
      return;
   }
   recursion(x, y, len / 2);                  //2사분면
   recursion(x + len / 2, y, len / 2);            //1사분면
   recursion(x, y + len / 2, len / 2);            //3사분면
   recursion(x + len / 2, y + len / 2, len / 2);   //4사분면
}

int main() {
   cin >> n;            // 2의 n제곱 크기
   cin >> r;            // x좌표
   cin >> c;            // y좌표
   recursion(0, 0, pow(2, n));      // pow  =  2의 n제곱

   return 0;
}