[백준] 1074번: Z

문제를 보자 예전에 한창 헤맸던 별 찍기 - 10와 비슷하게 재귀를 이용한 문제임을 알았다.

주어진 값에 맞는 마지막 한 칸만 남을 때까지 재귀적으로 행렬을 계속 4등분한다. 이때 각 행렬의 첫 번째(왼쪽 위) 값은 원래 행렬의 값에서 2^2(N-1)을 차례로 더한 값이다.

좌표 (r, c)가 4개의 행렬 중 어디에 있는지와 그 행렬에서의 상대적 좌표를 구한 후 N을 1 줄여 다시 함수를 호출한다. N이 0이 될 때 첫 번째 값이 답이 될 것이다.

import sys

sys.setrecursionlimit(10 ** 9)

N, R, C = map(int, sys.stdin.readline().split())


def find_number(n, left_top, r, c):
    if n == 0:
        print(left_top)
        return

    if r < 2 ** (n - 1):
        if c < 2 ** (n - 1):
            find_number(n - 1, left_top, r, c)
        else:
            find_number(n - 1, left_top + 2 ** (2 * (n - 1)) * 1, r, c - 2 ** (n - 1))
    else:
        if c < 2 ** (n - 1):
            find_number(n - 1, left_top + 2 ** (2 * (n - 1)) * 2, r - 2 ** (n - 1), c)
        else:
            find_number(
                n - 1,
                left_top + 2 ** (2 * (n - 1)) * 3,
                r - 2 ** (n - 1),
                c - 2 ** (n - 1),
            )


find_number(N, 0, R, C)