Z

출처 : 백준 #1074

시간 제한	메모리 제한
0.5초	512MB

---

문제

한수는 크기가 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

---

입출력 예시

예제 입력 1

2 3 1

예제 출력 1

11

---

예제 입력 2

3 7 7

예제 출력 2

63

---

풀이

생각

• 문제의 그림처럼 직접 배열을 생성하여 탐색한다면 시간이 너무 오래 걸린다.
• 한 변의 길이가 2^15인 배열을 만들어야 하기 때문이다.
• 따라서 직접 배열을 생성하기 보다는 일정한 규칙을 찾고, 그에 따라 탐색하기로 결정하였다.

풀이 설명

• 우선 2차원 배열을 중심으로 4등분을 할 수 있다.
• base는 현재 찾는 배열의 시작되는 숫자를 의미한다.
• r, c 즉 행과 열을 각각 [배열의 한 변의 길이]의 절반에 해당하는 수와 비교하여 좌상, 좌하, 우상, 우하 중 어디 쪽에 위치하는 지를 파악한다.
• 파악이 완료되면 base를 업데이트 해준다.
  • 좌상 -> 우상 -> 좌하 -> 우하
  • 위 순서대로 (2**(n-1))**2씩 증가한다고 보면됨
  • 좌상이라면 base에 변동이 없다.
• base를 업데이트 해줌과 동시에 r과 c 또한 업데이트를 하여 새로운 배열의 크기에 맞춰주어야 한다.
  • 우상 : c -= (2**n)//2 # 열 update
  • 좌하 : r -= (2**n)//2 # 행 update
  • 우하 : c -= (2**n)//2 # 열 update, r -= (2**n)//2 # 행 update

python code

# 백준 1074번 Z
from sys import stdin

def solution(n, r, c):
    base = 0
    while n > 1:
        # 행(row)이 2^n 절반보다 작다면
        if r < (2**n)//2:
            if c < (2**n)//2:           # 좌 상
                pass
            else:                       # 우 상
                base += (2**(n-1))**2 * 1
                c -= (2**n)//2 # 열 update

        else:   # r >= (2**n)//2        
            if c < (2**n)//2:           # 좌 하
                base += ((2**(n-1))**2) * 2
                r -= (2**n)//2 # 행 update

            else:                       # 우 하
                base += ((2**(n-1))**2) * 3
                # 행, 열 update
                r -= (2**n)//2
                c -= (2**n)//2
        n -= 1

    if r==0 and c==0:   # 좌 상
        return base
    elif r==0 and c==1: # 우 상
        return base+1
    elif r==1 and c==0: # 좌 하
        return base+2
    else:
        return base+3
    

input = stdin.readline
n, r, c = map(int, input().split())


print(solution(n, r, c))