2023-01-30 @이영훈
접근 방법
분할 정복으로 이 문제를 접근했습니다.
분할 정복 문제는 가장 쉬운 경우에 답을 구하고, 어려운 경우는 쉬운 경우로 분할해서 푸는 방식으로 접근합니다.
이 문제의 저의 접근 방법은 다음과 같습니다.
N이 1인지 확인합니다. N이 1이라면 2 x r + c 를 반환하고 종료합니다.
N이 2 이상이라면,
주어진 점(point)이 사사분면 중에서 몇 사분면에 있는 지 확인합니다.
그리고 해당 지점을 1/4 조각합니다.
•
만약 해당 점이 2^(n-1)보다 크다면 좌표를 업데이트(new_point 함수)합니다.
def new_point(point, n):
return point - 2 ** (n - 1)
Python
복사
•
해당 사분면까지의 거리를 더 합니다.
◦
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) 를 더합니다.
파이썬 코드
위의 접근 방법을 코드로 나타내면 다음과 같습니다
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)
Python
복사
모든 경우가 통과하고, 실제 정답입니다.