[Gold / 1074] Z

문제 링크

---

🔷 분류

분할 정복, 재귀

✒️ 문제 설명

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

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

다음은 N=3일 때의 예이다.

⬅️ 입력

첫째 줄에 정수 N, r, c가 주어진다.

➡️ 출력

r행 c열을 몇 번째로 방문했는지 출력한다.

💻 코드 (C++)

#include <iostream>
using namespace std;

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

  int half = 1 << (n - 1); // 2^(n-1)
  long long block = 1LL << (2 * n - 2);  // 한 사분면의 크기: half * half

  // 0번 사분면 (좌상)
  if (r < half && c < half)
    return RC(n - 1, r, c);
  // 1번 사분면 (우상)
  if (r < half && c >= half)
    return block + RC(n - 1, r, c - half);
  // 2번 사분면 (좌하)
  if (r >= half && c < half)
    return 2 * block + RC(n - 1, r - half, c);
  // 3번 사분면 (우하)
  return 3 * block + RC(n - 1, r - half, c - half);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N, r, c;
  cin >> N >> r >> c;

  cout << RC(N, r, c);
  return 0;
}