[Python/코테] 백준 1074 Z

1074 Z

문제 및 조건 설명: https://www.acmicpc.net/problem/1074

 

알고리즘 설계

💡idea.

사각형을 사등분하고, 각 부분에 같은 연산을 적용할 수 있으므로 재귀적으로 생각한다.

시간 제한이 0.5초이고 입력 제한이 1 ≤ N ≤ 15 이므로, 무작정 반복하면 시간/메모리 초과 오류를 마주하게 되니 주의하자.

 

🎲 step.

1. 함수의 형태

$(x, y)$로 시작하는 $n*n$ 크기의 사각형을 탐색하는 함수

def func(n, x, y)

 

2. base condition (종료 조건)

탐색을 시작하려는 사각형의 시작 좌표가 찾고자 하는 $(r, c)$와 동일할 때 종료

 

3. 재귀 

사등분한 사각형에 대해 같은 규칙(=재귀 함수)을 적용한다. 사각형이 한 칸씩 네 칸이 될 때까지 4등분하는 셈이다.

# [[1,2],
# [3,4]] 일 때,
N(n/2, x, y)		# 1 부분 (2사분면)
N(n/2, x, y+n/2)	# 2 부분 (1사분면)
N(n/2, x+n/2, y)	# 3 부분 (3사분면)
N(n/2, x+n/2, y+n/2)	# 4 부분 (4사분면)

알고리즘 구현

import sys

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

result = 0


# x, y는 현재 사분면의 시작 좌표, n은 변의 길이 -> 사분면으로 나누어 재귀적 호출하기 때문에 결국 n은 '탐색하려는' 변의 길이임.
def N(n, x, y):
    global result           # 이동 횟수

    if x == r and y == c:   # 찾고자 하는 위치일 때
        print(int(result))
        exit(0)             # 함수 종료

    if n == 1:              # 사분면을 나누다가 결국 한 칸에 도달했을 때
        result += 1         # 1 증가 후
        return              # 종료

    if not (x <= r < x+n and y <= c < y+n):
        result += n*n       # 사분면을 이동하면 기존 범위의 크기만큼 더해줌으로써 좌표가 시작됨
        return

    # [[1,2],
    # [3,4]] 일 때,

    # 1 부분 (2사분면)
    N(n/2, x, y)
    # 2 부분 (1사분면)
    N(n/2, x, y+n/2)
    # 3 부분 (3사분면)
    N(n/2, x+n/2, y)
    # 4 부분 (4사분면)
    N(n/2, x+n/2, y+n/2)


N(2**n, 0, 0)