[class3] (백준 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열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2^N

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

예제 입력 4

4 7 7

예제 출력 4

63

예제 입력 5

10 511 511

예제 출력 5

262143

예제 입력 6

10 512 512

예제 출력 6

786432

힌트

 

출처

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: hmw9309

#include <iostream>
#include <cmath>
using namespace std;
int GetNum(int r, int c, int len)
{
    if (len <= 0)
        return 0;

    int mid = pow(2, len - 1);

    if (r < mid && c < mid)
    {
        return GetNum(r, c, len - 1);
    }
    else if (r >= mid && c < mid)
    {
        return mid * mid * 2 + GetNum(r - mid, c, len - 1);
    }
    else if (r < mid && c >= mid)
    {
        return mid * mid + GetNum(r, c - mid, len - 1);
    }
    else if (r >= mid && c >= mid)
    {
        return mid * mid * 3 + GetNum(r - mid, c - mid, len - 1);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, r, c, len;
    cin >> N >> r >> c;
    cout << GetNum(r,c,N);
    return 0;
}