[백준] [Python] 1074번 Z - 재귀

www.acmicpc.net/problem/1074

1074번: Z

 

 

Python

import sys

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

def z(n, r, c):
    area = 4**(n-1)
    half = 2**(n-1)
    if n==1:
        return 2*r+c
    
    if r<=half and c>half:
        return area*1 + z(n-1,r,c-half)
    elif r<=half and c<=half:
        return z(n-1,r,c)
    elif r>half and c<=half:
        return area*2 + z(n-1,r-half,c)
    elif r>half and c>half:
        return area*3 + z(n-1,r-half,c-half)
print(z(n,r+1,c+1)-3)

ㅈ

 

짧은 풀이

• 1,2,3,4 사분면 중 어느 곳에 위치한 지에 따라 한 칸짜리로 줄어들 때까지 해당 단계에서 지나쳐야 하는 칸 수를 누적해간다.
• n일 때 면적은 4^n. 그러나 해당 위치에 가기에 얼마나 필요한지 구하기에 1/4인 4**(n-1)을 구했다.
• 자신이 위치한 곳에 따라 면적을 몇번 곱하여 더할지 정한다.
• 점점 작아지는 구획에 맞추어 찾아야하는 행열 위치도 반씩 감소시켜준다.
• 0번 인덱스를 고려하지 않기 위해 함수를 실행할 때 r, c에 +1씩 해준다
  • 해당 좌표가 현재 위치에서 반을 넘겼는지 확인하며 그 위치를 확인한다.
  • 얼결에 0,0 좌표 처리도 말끔해졌다.