최단경로1 [백준] 12913: 매직 포션 - JAVA https://www.acmicpc.net/problem/12913 풀이0번 도시에서 1번 도시까지 가장 빠른 시간에 가야 한다. 포션을 마실 수 있는데 마시게 되면 한 도시에서 다른 도시로 이동하는데 드는 시간을 반으로 줄일 수 있다. n개의 도시, 포션 사용 가능 개수 k가 주어진다. 즉, 이차원배열을 `dist[n][k + 1]`로 선언하여 포션을 사용한 개수마다 체크해주어야 한다. 우선 도시마다 걸리는 시간이 모두 양수이기 때문에 0번 도시부터 모든 도시까지 최소 시간을 구할 수 있는 다익스트라 알고리즘을 적용했다. 다음 도시로 이동할 때 포션을 쓰지 않는 경우, 쓰는 경우를 나눠 진행해야 한다. 포션을 쓰는 경우는 현재 도시에 오는데 쓰인 포션의 개수가 k보다 작은 경우에만 가능하다. 메모리:.. 2024. 9. 10. 이전 1 다음