[BaekJoon] 1074번: Z (Python)

• 어떻게든 return문으로 해보려 머리 싸맸는데 불가능했다.

Solution

import sys


def solution(N: int, r: int, c: int) -> None:
    answer = 0

    def quad_tree(n: float, x: float, y: float) -> None:
        nonlocal answer

        # (r, c) 좌표가 있는 곳을 찾아내서 존재하면 출력 후 프로그램 종료
        if r == x and c == y:
            print(int(answer))
            exit(0)

        # 현재 처리하고 있는 사각형의 영역이 (r, c) 좌표를 포함하지 않는지 확인
        if not (x <= r < x + n and y <= c < y + n):
            # 현재 사각형의 크기(n)를 제곱하여 계쏙 answer에 누적시킴
            # 이건 현재 사각형을 더 이상 나눌 필요가 없는 경우,
            # (r, c)를 포함하지 않는 사각형의 크기를 누적하여 해당 사각형을 건너뛰게 만드는 역할을 함
            answer += n * n
            return

        # 쿼드 트리 알고리즘 사용하여 4개의 작은 사각형(사분면)으로 나눔
        # 호출할 때마다 n을 절반으로 줄임
        mid = n / 2
        quad_tree(mid, x, y)
        quad_tree(mid, x, y + mid)
        quad_tree(mid, x + mid, y)
        quad_tree(mid, x + mid, y + mid)

    quad_tree(2 ** N, 0, 0)


N, r, c = map(int, sys.stdin.readline().rstrip().split())
solution(N, r, c)

Reference

• https://www.acmicpc.net/problem/2630