[Baekjoon] 1074. Z

# Problem

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 제한 1 ≤ N ≤ 15 0 ≤ r, c < 2N

 

# My Answer

n, r, c = map(int,input().split())
def Z(n,r,c):
    if n==1:
        z = [[0,1],[2,3]]
        return z[r][c]
    else:
        if r >= (2**n)//2 and c>= (2**n)//2 :
            return (4**(n-1))*3 + Z(n-1,r-(2**n)//2,c-(2**n)//2)
        elif r >= (2**n)//2 and c< (2**n)//2:
            return (4**(n-1))*2 + Z(n-1,r-(2**n)//2,c)
        elif r < (2**n)//2 and c>= (2**n)//2:
            return (4**(n-1)) + Z(n-1,r,c-(2**n)//2)
        else:
            return Z(n-1,r,c)
    
print(Z(n,r,c))

 

# Solution 1

def solve(n, x, y): 
    global result
    if n == 2:
        if x == X and y == Y:
            print(result)
            return
        result += 1
        if x == X and y + 1 == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y + 1 == Y:
            print(result)
            return
        result += 1
        return
    solve(n / 2, x, y)
    solve(n / 2, x, y + n / 2)
    solve(n / 2, x + n / 2, y)
    solve(n / 2, x + n / 2, y + n / 2)
    
result = 0
N, X, Y = map(int, input().split(' ')) 
solve(2 ** N, 0, 0)

 

# Solution 2

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

def Z(sz, x, y):
    if sz ==1:
        return 0
    sz //=2
    for i in range(2):
    	for j in range(2):
            if x<sz * (i+1) and y < sz * (j+1):
                return (i*2+j) * sz*sz + Z(sz, x-sz*i, y-sz*j)
            
print(Z(2**N, r, c))