[파이썬][백준] 1074번: Z

1. 문제

문제 유형: 재귀 함수

 

• 주어진 조건대로 정사각형을 방문하면서 원하는 좌표가 나오면 몇 번째로 방문했는지 출력
• n <= 15 이므로 최대 $2^{15} * 2^{15}$의 사각형이 생기므로 조건을 정해 주어야 함.
  • 해당 범위 내에 있는 사각형 안에 찾고자 하는 좌표가 없을 경우 그 범위 내에 있는 총 사각형 수만큼 방문 횟수에 누적
• n = 3에서 (7,7)을 찾을 때 1) 빨간색 영역, 2) 초록색 영역, 3) 파란색 영역에 해당하지 않으므로 각 영역의 사각형 수를 방문 횟수에 누적

• 그 다음도 마찬가지로 남은 영역을 쪼갠 후 반복

• 그 후 n = 1이 되면 한 칸씩 돌면서 좌표를 찾아가면서 방문 횟수를 누적함

2. 소스코드

import sys

result = 0


def z(n, x, y):
    global result
    if x == r and y == c:
        print(int(result))
        exit(0)

    if n == 1:
        result += 1
        return

    if not (x <= r < x + n and y <= c < y + n):
        result += n * n
        return
    z(n / 2, x, y)
    z(n / 2, x, y + n / 2)
    z(n / 2, x + n / 2, y)
    z(n / 2, x + n / 2, y + n / 2)


n, r, c = map(int, sys.stdin.readline().split(' '))
z(2 ** n, 0, 0)