[C++ / 1074] Z

문제

1074번: Z

---

문제 설명

크기가 2^N x 2^N 인 2차원 배열을 Z모양으로 탐색하려고 한다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

---

풀이 방식

해당 문제는 분할 정복과 관련된 문제이다.

 

배열을 Z 모양으로 다음과 같이 탐색순서가 매겨진다.

n = 1 일때

n = 2 일때

n = 2 일때의 그림을 잘 살펴 보면 Z는 일정한 범위를 순차적으로 탐색하고 있다.

그래서 이를 Z의 탐색순서 대로 1~4사분면으로 쪼갠뒤 (5,3)을 방문할때의 탐색순서를 찾으려고 하면 다음과 같다.

 

2^Nx2^N의 한 사분면의 크기는 2^N-1x2^N-1로 한 변을 2로 나눈 크기가 된다.

 

그런데 이때 한 사분면의 크기는 한 사분면의 탐색 횟수로도 사용이 가능하다.

이 말은 즉, 1사분면의 영역에 찾고자 하는게 없다면 1사분면의 크기만큼의 탐색이 진행된 셈이다.

 

위 예제에서 보면 2³x2³ 에서 찾고자 하는 것이 3사분면에 있다.

그럼으로 1사분면과 2사분면을 지났음으로 16+16을 해준다.

 

다음과 같은 방식으로 풀이를 진행하면 된다.

---

솔루션

#include <iostream>
#include <cmath>

using namespace std;

int n, r, c;
int ans;

void Z(int y, int x, int size)
{
  if (y == r && x == c)
  {
    cout << ans << '\n';
    return;
  }

  if (r < y + size && r >= y && c < x + size && c >= x)
  {
    Z(y, x, size / 2);
    Z(y, x + size / 2, size / 2);
    Z(y + size / 2, x, size / 2);
    Z(y + size / 2, x + size / 2, size / 2);
  }
  else
  {
    ans += size * size;
  }
}
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> r >> c;
  Z(0, 0, pow(2, n));
  return 0;
}