[Python] 백준1074 Z

14 Jan 2023 in Study on Algorithm

백준1074 Z 링크

문제

예제 입력

---

코드

import sys

result = 0
flag = False
def z(n, x, y):
    global result, flag

    if flag :
        return
    
    if x == r and y == c:
        flag = True
        return
    # 해당 좌표가 아닐 때
    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)
print(result)

설명

파이썬을 통해서 사용자로부터 입력받아 재귀함수를 사용하여 사분면으로 나누어 좌표가 있는지 확인하는 분할정복 알고리즘으로 Z를 구현했습니다.

---

정리

n,r,c=map(int,input().split())
def sol(n,r,c):
    if n==0:
        return 0
    # (0, 2) = 4 / (0, 4) = 16 / (1, 2) = 6 / (2, 4) = 24
    # 2의 배수가 아닐 때 + 2의 배수로 만든 4배 비율
    return 2*(r%2)+(c%2) + 4*sol(n-1,int(r/2),int(c/2))

print(sol(n,r,c))

그 외에도 점화식을 만들어 구현할 수 있습니다.

---

결과