1. Problem 📃

📚 출처 - 1074 - Z

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

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

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

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

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

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

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N
  0
  입출력 예

예제 입력	예제 출력
2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

2. Logic 👨‍🏫

예를 들어, N=3, r=7, c=7를 입력 받았다고 가정한다면 답으로 도출되어야 하는 값은 63이다. 이 과정을 한번 살펴봐보자.

먼저 이렇게 4개의 영역으로 분할했을 때 규칙을 살펴보면
처음 (7, 7)은 N=3인 영역에서 제4사분면에 해당됩니다.
(가로 좌표 7 >= 2의 2승, 세로 좌표 7 >= 2의 2승이므로 제4사분면)

• 제1사분면은 0부터 시작
• 제2사분면은 16
• 제3사분면은 32
• 제4사분면은 48부터 시작

두 번째로 쪼갰을때는 (7, 7)의 좌표는 (3, 3)이 됩니다.
(가로 세로가 각각 네칸씩 줄어드니깐, 7 - 2의 2승 = 3)

또한 (3, 3)은 N = 2인 영역에서 제4사분면에 해당됩니다.
(3 >= 2의 1승, 3 >= 2의 1승이므로 제 4사분면)

48을 뺐다고 가정한다면, 제4 사분면은 12부터 시작합니다.

세 번째로 쪼개면 (3, 3)의 좌표는 (1, 1)로, 제 4사분면에 해당합니다.
(가로 세로 두 칸씩 줄어드니깐, 3 - 2의1승 = 1)

제 4사분면인 (1, 1)은 3입니다.

그래서 48 + 12 + 3은 63입니다.

3. Code 💻

1. 참고해서 이해해 푼 코드 😁

N, r, c = map(int, input().split())
ans = 0

while N != 0:
    N -= 1
    size = 2 ** N
    if r < size and c < size: # 1사분면
        ans += (size) * (size) * 0
        
    elif r < size and c >= size: # 2사분면
        ans += (size) * (size) * 1
        c -= size

    elif r >= size and c < size: # 3사분면
        ans += (size) * (size) * 2
        r -= size

    else: # 4사분면
        ans += (size) * (size) * 3
        c -= size
        r -= size

print(ans)