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)모든 경우가 통과하고, 실제 정답입니다.


