파이썬으로 두 리스트의 마지막 인덱스에 도달하는 최소 비용 구하기

문제 개요

길이가 같은 두 개의 숫자 리스트 nums0과 nums1, 그리고 거리를 의미하는 d와 비용을 의미하는 c가 주어집니다. 우리는 nums0 또는 nums1 중 한쪽의 인덱스 0에서 출발하여, 어느 한쪽 리스트의 마지막 인덱스에 도달해야 합니다.

매 단계마다 비용 c를 지불하면 다른 리스트로 전환할 수 있고, 그 후에는 최대 d만큼 앞으로 점프할 수 있습니다. 이때 특정 인덱스에 착지하면 해당 위치의 값을 비용으로 지불해야 합니다. 목표는 작업을 완료하는 데 드는 최소 총비용을 구하는 것입니다.

입력 및 출력 예시

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

nums0 = [2, 3, 10, 10, 6], nums1 = [10, 10, 4, 5, 100], d = 2, c = 3

이 경우 출력은 18이 됩니다. 첫 번째 리스트의 값 2에서 출발한 뒤, 두 번째 리스트의 4로 전환하고, 다시 첫 번째 리스트의 6으로 되돌아오는 경로가 최적입니다. 착지 비용은 2 + 4 + 6 = 12이며, 리스트를 두 번 전환할 때마다 비용 3씩 발생하므로 총비용은 12 + 6 = 18입니다.

해결 알고리즘

이 문제는 재귀적으로 모든 가능한 경로를 탐색하면서 최솟값을 찾는 방식으로 해결할 수 있습니다. 각 위치에서 "현재 리스트에 머물러 점프"하는 경우와 "비용을 내고 다른 리스트로 전환한 뒤 점프"하는 경우를 모두 고려합니다. 구체적인 절차는 다음과 같습니다.

1. switch: 키 0에는 nums0을, 키 1에는 nums1을 저장하는 딕셔너리를 만듭니다.
2. search() 함수를 정의합니다. 이 함수는 현재 인덱스 idx와 리스트 번호 nums를 매개변수로 받습니다.
3. idx가 switch[nums]의 크기보다 크거나 같으면 무한대(inf)를 반환합니다.
4. idx가 마지막 인덱스(크기 - 1)와 같으면 switch[nums][-1] 값을 반환합니다.
5. 임시 변수 c를 무한대로 초기화합니다.
6. i를 1부터 dist + 1까지 반복하면서 다음 두 가지 경우의 최솟값을 계산합니다.
   • 같은 리스트에 머무르는 경우: switch[nums][idx] + search(idx + i, nums)
   • 다른 리스트로 전환하는 경우: switch[nums][idx] + cost + search(idx + i, 반전된 nums)
7. c를 반환합니다.
8. 메인 로직에서는 min(search(0, 0), search(0, 1))을 반환하여 두 리스트에서 시작하는 경우 중 더 작은 값을 선택합니다.

파이썬 구현 예제

이해를 돕기 위해 다음 구현을 살펴보겠습니다.

class Solution:
    def solve(self, nums0, nums1, dist, cost):
        switch = {0: nums0, 1: nums1}
        def search(idx, nums):
            if idx >= len(switch[nums]):
                return float("inf")
            if idx == len(switch[nums]) - 1:
                return switch[nums][-1]
            c = float("inf")
            for i in range(1, dist + 1):
                c = min(c, switch[nums][idx] + search(idx + i, nums))
                c = min(c, switch[nums][idx] + cost + search(idx + i, int(not nums)))
            return c
        return min(search(0, 0), search(0, 1))

ob = Solution()
nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3
print(ob.solve(nums0, nums1, d, c))

입력

[2, 3, 10, 10, 6],[10, 10, 4, 5, 100], 2, 3

출력

18

참고: 성능 최적화 팁

위 구현은 가능한 모든 경로를 재귀적으로 탐색하기 때문에 리스트의 길이가 길어지면 실행 시간이 기하급수적으로 증가할 수 있습니다. 실전 환경에서는 functools.lru_cache 등을 활용해 메모이제이션을 적용하는 것이 좋습니다. (인덱스, 리스트) 상태를 한 번씩만 계산하면 되므로 시간 복잡도를 O(n × d) 수준으로 크게 줄일 수 있습니다.