[baekjoon] 백준 1074번(파이썬): Z

문제

1074번: Z

알고리즘

- 큰 사각형(배열)부터 작은 사각형(배열)으로 재귀 함수를 통해 탐색한다.

- 탐색 중인 배열 중에 찾는 좌표가 없다면 좌표에 크기를 더한다. => 더 이상 탐색할 필요 없는 사각형(배열)이기 때문.

- 찾는 좌표라면 res를 출력하고 종료한다.

코드

import sys


def visited(n, r, c):
    global res

    # 찾는 좌표라면 res를 출력하고 종료
    if r == R and c == C:
        print(int(res))
        exit(0)

    # 탐색 증인 배열 중에 찾는 좌표가 없다면 좌표에 크기를 더한다.
    if not (r <= R < r + n and c <= C < c + n):
        res += n * n
        return

    # 1/2/3/4사분면을 재귀적으로 탐색
    visited(n/2, r, c) # 1사분면
    visited(n/2, r, c + n/2) # 2사분면
    visited(n/2, r + n/2, c) # 3사분면
    visited(n/2, r + n/2, c + n/2) # 4사분면


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

# 2^n을 0, 0부터 탐색
visited(2 ** N, 0, 0)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법