문제

입력 출력 예시

해결 방법

문제에서 나온 예시로 해결 방법을 생각해보자.

1번 도시에서 4번 도시까지 가는 최소 비용을 찾기 위해서 어떻게 해야 할까?

답은 각 도시를 방문할 때마다 그 전까지 도시 중 리터당 가격이 가장 싼 기름을 넣어서 가야 한다.

예제를 직접 해결하며 정리해보면

1. 1번 도시에서 2번 도시로 가기 위해서는 현재 기름양이 0이기 때문에 무조건 기름을 넣어야 한다. 따라서 5원/km * 2km = 10원
2. 2번 도시에서 3번 도시로 가기 위해서 1번 도시와 2번 도시의 기름 가격을 비교해보자. 2번 도시는 1번 도시보다 기름값이 싸다. 굳이 1번 도시에서 더 비싼 가격을 주고 3번 도시까지 갈 기름을 채울 필요 없이, 2번 도시에서 한 번 더 주유해서 3번 도시까지 가는데 필요한 기름을 채우면 된다. 따라서 2원/km * 3km = 6원
3. 3번 도시에서 4번 도시로 가기 위해서 1번, 2번, 3번 도시의 기름 가격을 비교해보자. 2번 도시의 기름 가격이 2원/km로 가장 싸다. 즉 3번 도시에서 4번 도시로 갈 기름은 2번 도시에서 주유하는 것이 가장 적합하다. 따라서 2원/km * 1km = 2원
4. 위 세 가격을 합치면 10 + 6 + 2 (원) = 18원이 된다.