백준_1074_Z

백준 1074번 문제입니다.

 

 

 

 

행렬에서 z모양으로 탐색하는 문제입니다.

 

이 문제는 입력받은 행(r)과 열(c)의 크기에 따라 위치를 판단할 수 있습니다.

 

위 행렬을 사분면 나누듯 4등분을 하며 재귀적으로 문제를 해결할 수 있을 것 같습니다.

 

( 입력받은 행과 열이 어디에 위치한지 찾고 또 4등분하고를 반복 )

 

 

코드)

입력받은 행과 열이

1.좌상단

2.우상단

3.좌하단

4.우하단

중 어디에 있는지 파악하고,

 

재귀를 이용하여 그 부분으로 다시한번 쪼개는 방식을 사용.

(위치에 따라 return 할 떄 재귀함수에 더해지는 값이 달라지는 것 중요 -> 2의 거듭제곱을 이용하여 표현 가능)

#include <cmath>
#include <iostream>

int Z(int n, int r, int c) {
  if (n == 0) return 0;

  int half = pow(2, n - 1);

  if (r < half && c < half)
    return Z(n - 1, r, c);
  else if (r < half && c >= half)
    return pow(2, 2 * n - 2) + Z(n - 1, r, c - half);
  else if (r >= half && c < half)
    return pow(2, 2 * n - 1) + Z(n - 1, r - half, c);

  return 3 * pow(2, 2 * n - 2) + Z(n - 1, r - half, c - half);
}

int main(void) {
  int n, r, c;
  std::cin >> n >> r >> c;

  std::cout << Z(n, r, c) << '\n';

  return 0;
}