문제 링크

<aside> 💡 0-1 너비 우선 탐색/데이크스트라/다이나믹 프로그래밍/그래프 이론/수학

</aside>

Memory 117368KB Time 372ms Code Length 482B

import sys, heapq
input = sys.stdin.readline
m = int(input())
n = int(input())
a = list(map(int, input().split()))
s = max(a)
dp = [float('inf') for i in range(s)]
dp[0] = 0
pq = [(0, 0)]
while pq:
    tdis, tpos = heapq.heappop(pq)
    if dp[tpos] != tdis:
        continue
    for i in range(n):
        t = tpos + a[i]
        if dp[t % s] > tdis + 1 - t // s:
            dp[t % s] = tdis + 1 - t // s
            heapq.heappush(pq, (dp[t % s], t % s))
print(dp[m % s] + m // s)

이 코드는 최소 비용으로 목표 지점에 도달하는 문제를 해결하는 것이다.

먼저 sys와 heapq 라이브러리를 불러온다.

m은 목표 지점, n은 이동할 수 있는 거리의 개수, a는 이동할 수 있는 거리를 나타낸다.

dp 리스트는 각 위치에 도달하는데 필요한 최소 비용을 저장한다.

pq는 우선순위 큐로, 현재 위치와 그 위치에 도달하는데 든 비용을 저장한다.

우선순위 큐에서 가장 비용이 적은 위치를 가져와서 그 위치에 도달하는데 든 비용이 dp에 저장된 비용과 같다면 그 위치에서 이동할 수 있는 거리만큼 이동한다.

이동한 위치에 도달하는데 든 비용이 dp에 저장된 비용보다 작다면 dp를 갱신하고 그 위치와 비용을 우선순위 큐에 넣는다.

이 과정을 반복하여 목표 지점에 도달하는데 필요한 최소 비용을 구한다.