소스코드

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

def z(n,r,c):
	if n == 0:
		return 0
	
	if r < 2**(n-1) and c < 2**(n-1):
		# 1사분면
		return z(n-1, r, c) + 0
	elif r < 2**(n-1) and c > 2**(n-1):
		# 2사분면
		return z(n-1, r, c - 2**(n-1)) + ((2**(n-1)) * (2**(n-1)))
	elif r > 2**(n-1) and c < 2**(n-1):
		# 3사분면
		return z(n-1, r - 2**(n-1), c) + ((2**(n-1)) * (2**(n-1))) * 2
	else:
		# 4사분면
		return z(n-1, r - 2**(n-1), c - 2**(n-1)) + ((2**(n-1)) * (2**(n-1))) * 3

result = z(N,r,c)
sys.stdout.write(f"{result}\\n")

풀이

일단 재귀함수인건 누구나 눈치챌 듯 합니다(문제가 반복된다는 것도 보일테고, 문제에도 ‘재귀적으로’라고 적혀있기 때문).

재귀함수에 기저 조건은 빠질 수 없죠. 기저 조건은 n이 0이 되는 경우입니다. 2^0은 1이니까요.

이제 어떻게 재귀적으로 함수를 실행할 지를 생각하면 될 듯 합니다. 풀이가 되게 다양한 것 같은데, 저는 1 ~ 4사분면의 영역을 조건으로 걸어서 재귀적으로 실행했습니다. r과 c가 변하는 이유는 재귀적으로 실행된 경우, 2차원 배열의 사이즈가 작아지기 때문에 상대적인 위치를 조정해야하기 때문입니다.

그렇다면 이제 방문 순서 숫자를 어떻게 리턴해야할지 고민해야합니다. 저는 이렇게 생각했습니다 :

4사분면은 나머지 1~3사분면의 사이즈만큼을 더한거잖아? 2사분면은 1사분면의 사이즈만큼을 더하면 되네.

그래서 재귀함수 실행 옆에 (각 사분면의 사이즈 * 필요횟수)를 더해줬습니다.