데카르트 좌표평면의 원점 (0, 0)에 있다고 가정해 보겠습니다. 우리는 단위 길이의 수평 이동(H)과 수직 이동(V)만을 사용하여 점 (x, y)로 이동하려고 합니다. 목적지에 도달할 수 있는 경로는 여러 가지가 있으며, 각 경로는 여러 번의 H 이동과 V 이동의 순서로 구성됩니다. 예를 들어, (0, 0)에서 (2, 2)로 이동할 때 "HVVH"는 가능한 경로 중 하나입니다.
여기에 값 k가 추가로 주어진다면, 사전순(lexicographic order)으로 k번째로 작은 이동 경로를 찾아야 합니다.
예를 들어 입력이 (x, y) = (3, 3), k = 3이라면 결과는 "HHVVVH"가 됩니다.
해결 전략
이 문제는 조합(combination) 계산을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- paths(a, b): a번의 H 이동과 b번의 V 이동으로 만들 수 있는 총 경로의 수를 계산합니다. 이는 이항계수 C(a+b, a)와 같으며, 팩토리얼을 이용해 구할 수 있습니다.
- 각 단계에서 'H'를 선택했을 때 남은 경로의 수(n)를 계산합니다. k가 n보다 작다면 k번째 경로는 반드시 'H'로 시작하므로 'H'를 선택합니다.
- k가 n보다 크거나 같다면 'H'로 시작하는 경로들을 모두 건너뛰고, k에서 n을 빼준 뒤 'V'를 선택합니다.
구현 단계
이를 해결하기 위해 다음 단계를 따릅니다.
- paths() 함수를 정의합니다. 이 함수는 x, y를 인자로 받습니다.
- min(x, y) < 0이면 0을 반환합니다.
- 그렇지 않으면 factorial(x+y) / factorial(x) / factorial(y)을 반환합니다.
- 메인 메서드에서 다음을 수행합니다.
- res := 새로운 리스트
- (p, q) := (0, 0)
- (p, q)가 (x, y)와 같아질 때까지 반복합니다:
- n := paths(x - p - 1, y - q)
- p + 1 <= x이고 k < n이면 res 끝에 'H'를 추가하고 p를 1 증가시킵니다.
- 그렇지 않으면 k -= n을 수행하고, res 끝에 'V'를 추가한 뒤 q를 1 증가시킵니다.
- res의 문자들을 연결하여 반환합니다.
예제 코드
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
from math import factorial
def paths(x, y):
if min(x, y) < 0:
return 0
return factorial(x+y) / factorial(x) / factorial(y)
def solve(x, y, k):
res = []
p, q = 0, 0
while (p, q) != (x, y):
n = paths(x - p - 1, y - q)
if p + 1 <= x and k < n:
res.append('H')
p += 1
else:
k -= n
res.append('V')
q += 1
return ''.join(res)
(x, y) = (3, 3)
k = 3
print(solve(x, y, k))
입력
(3, 3), 3
출력
HHVVVH