[알고리즘] 백준 1074번 Z 파이썬 python
💤

[알고리즘] 백준 1074번 Z 파이썬 python

Created
2023/01/30
Tags
Algorithm
Python
Divide And Conquer
Recursive
 
2023-01-30 @이영훈
 
 
 

접근 방법

분할 정복으로 이 문제를 접근했습니다.
분할 정복 문제는 가장 쉬운 경우에 답을 구하고, 어려운 경우는 쉬운 경우로 분할해서 푸는 방식으로 접근합니다.
 
이 문제의 저의 접근 방법은 다음과 같습니다.
N이 1인지 확인합니다. N이 1이라면 2 x r + c 를 반환하고 종료합니다.
 
N이 2 이상이라면,
주어진 점(point)이 사사분면 중에서 몇 사분면에 있는 지 확인합니다.
그리고 해당 지점을 1/4 조각합니다.
  • 만약 해당 점이 2^(n-1)보다 크다면 좌표를 업데이트(new_point 함수)합니다.
    • Python
      def new_point(point, n):
          return point - 2 ** (n - 1)
  • 해당 사분면까지의 거리를 더 합니다.
    • 1/4 조각한 사분면의 거리는 2^(n-1) * 2^(n-1) 입니다. 그래서 각 사분면마다 Z 거리를 더합니다.
    • 1사분면이라면 2^(n-1) * 2^(n-1) 을 더하고,
    • 2사분면이라면 0 * 2^(n-1) * 2^(n-1) = 0 을 더하고, (즉, 안 더 합니다)
    • 3사분면이라면 2 * 2^(n-1) * 2^(n-1) 를 더하고
    • 4사분면이라면 3 * 2^(n-1) * 2^(n-1) 를 더합니다.
 
 

파이썬 코드

위의 접근 방법을 코드로 나타내면 다음과 같습니다
 
Python
import sys

input = sys.stdin.readline

n, r, c = map(int, input().split())


def new_point(point, n):
    return point - 2 ** (n - 1)


def dnc(n, r, c):
    if n == 1:
        return 2 * r + c

    # 2사분면
    if r < 2 ** (n - 1) and c < 2 ** (n - 1):
        return dnc(n - 1, r, c)
    # 1사분면
    elif r < 2 ** (n - 1) and c >= 2 ** (n - 1):
        return 2 ** (2 * n - 2) + dnc(n - 1, r, new_point(c, n))
    # 3사분면
    elif r >= 2 ** (n - 1) and c < 2 ** (n - 1):
        return 2 ** (2 * n - 1) + dnc(n - 1, new_point(r, n), c)
    # 4사분면
    else:
        return 3 * 2 ** (2 * n - 2) + dnc(n - 1, new_point(r, n), new_point(c, n))


print(dnc(n, r, c))
 
 
 
가볍게 테스트를 해보면
Python
# test code
print(dnc(2, 0, 0) == 0)
print(dnc(2, 0, 1) == 1)
print(dnc(2, 1, 0) == 2)
print(dnc(2, 1, 1) == 3)

print(dnc(2, 0, 2) == 4)
print(dnc(2, 0, 3) == 5)
print(dnc(2, 1, 2) == 6)
print(dnc(2, 1, 3) == 7)

print(dnc(2, 2, 0) == 8)
print(dnc(2, 2, 1) == 9)
print(dnc(2, 3, 0) == 10)
print(dnc(2, 3, 1) == 11)

print(dnc(2, 2, 2) == 12)
print(dnc(2, 2, 3) == 13)
print(dnc(2, 3, 2) == 14)
print(dnc(2, 3, 3) == 15)
모든 경우가 통과하고, 실제 정답입니다.