문제

1074번 Z

풀이

이 문제의 핵심은 재귀(recursion)로 반복되는 구조를 얼마나 잘 해체하는지에 있다. 한 변의 길이는 항상 2의 거듭제곱꼴로 주어지며, 그에 따라 항상 각 변의 중선을 이어서 4개의 공간으로 분리되는 것을 알 수 있다. 이는 한 변의 길이가 21일 때 4개의 공간이 0, 1, 2, 3이 될 때까지 만족한다.

주어진 열이 변의 중심에 대해 왼쪽에 있는지 오른쪽에 있는지, 주어진 행이 변의 중심에 대해 위쪽에 있는지 아래쪽에 있는지 판단하기 위해서 행//2n-1, 열//2n-1를 계산해 준 다음(0,0),(0,1),(1,0),(1,1) 중 무엇인지 판단한다.

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 각각 2n-1의 제곱의 몇 배를 더해줘야되는지 return부분에서 결정해준다.

재귀의 종료조건은 n=0일 때, 즉, 길이가 1인 1칸짜리 정사각형의 번호가 0인 것으로 해준다.

코드

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

def f(n,r,c):
  if n==0: return 0
  new = 2**(n-1)
  a,b=r//new,c//new
  r,c=r-a*new,c-b*new
  if a+b==0:
    return f(n-1,r,c)
  elif a+b==2:
    return f(n-1,r,c)+new**2*3
  else:
    if b==1:return f(n-1,r,c)+new**2*1
    else:return f(n-1,r,c)+new**2*2

print(f(n,r,c))