수열의 일반항 발견해서 대입하면 되는 문제였다.

1. N <= 15, 2^15 = 1024 * 32 = 32000 * 32000
다 구할 순 없어 그냥 연산 방법을 구해야해

2. order[r][c] = i
N = 2였을 때, r = 3, c = 3이면 15인데
r == 0, 1 이면 상단. 즉 r < 2^(N-1)
r == 2, 3 이면 하단 r >= 
c == 0, 1 이면 좌단 c <
c == 2, 3 이면 우단 c >=

다음 걸 보기 위해 15 // 4를 했는데 4는 2^2(N-1)

좌상단: i = 0 * 2^2(N-1)
    의 좌상단: + 0 * 2^2(N-2)
        ...        + 0 * 2^2(0)
우상단: 1 * 2^N
좌하단: 2 * 2^N
우하단: 3 * 2^N

3. 반복 또는 재귀

4. 엣지 케이스
경계값 주의

느낀 점: 재귀 머리아프니 최대한 반복으로

재귀

탑다운, 첫 풀이

import sys
input = sys.stdin.readline
N, r, c = map(int, input().split())

def order(n, r, c):
    if (n == 0):
        return 0
    div = 0
    if r // 2 ** (n-1) > 0:
        div += 2
    if c // 2 ** (n-1) > 0:
        div += 1
        
    return order(n - 1, r % 2**(n - 1), c % 2**(n - 1)) + div * 2**(n - 1) * 2**(n - 1)

print(order(N, r, c))

탑다운, 일반항 slided

def order(N, r, c):
    N -= 1
    if N == 0: 
    	return 0
    div = 2 * (r // 2**N) + c // 2**N
    return order(N, r % 2**N, c % 2**N) + div * 2**N * 2**N
    
print(order(N, r, c))

바텀업

def order(n, r, c):
    if (n == 0):
        return 0
    return order(n - 1, r // 2, c // 2) * 2 * 2 + (r % 2) * 2 + (c % 2)

print(order(N, r, c))

반복

탑다운

ans = 0

while(N--):
    div = 2 * (r // 2**N) + c // 2**N
    ans += div * 2**N * 2**N
    r %= 2 ** N
    c %= 2 ** N

print(ans)

바텀업

ans = 0

for i in range(N):
    div = 2 * (r % 2) + c % 2
    ans += div * 2**i * 2**i
    r //= 2
    c //= 2
    
print(ans)