boj_13305_주유소

https://www.acmicpc.net/problem/13305 <풀이> 문제에서 구하자고 하는 것은 "가장 왼쪽 도시에서 부터 가장 오른쪽 도시까지의" 최소비용이다. 우리가 상식적인 선에서 최소비용으로 어떤 미션을 수행하기 위해선, 최소비용으로 최고의 효율을 뽑아야 한다.

이 문제의 특징을 살펴보면 쉽게 알 수 있다. 이 문제는 무조건 "왼쪽"에서 "오른쪽"으로 순차적으로 도시를 방문해야 한다.

따라서, 어떤 도시에 가기 위해선 이전(왼쪽) 도시에서 충분한 주유를 해야한다. 만약 다음 도시의 주유가격이 그 이전(왼쪽)의 어떤 도시의 주유가격보다 비싸다면 나는 그 도시에서의 주유를 피하기 위해 그 이전의 어떤..........