13305번 주유소(그리디) - ☆

#문제링크 : www.acmicpc.net/problem/13305

<전략>

1. 처음엔, 도시 중 가장 싼 도시를 찾아 그 도시부터 뒤로 쭉 그 가격으로 구매, 도시 범위를 처음~가장 싼 도시로 수정하고 다시 그중에 가장 싼 도시를 찾아 그 도시부터 수정된 범위의 마지막 도시까지 그 가격으로 구매 ... 이런식으로 했었는데, 답은 맞았지만 시간초과가 나왔다.

2. 1의 과정은 뒤에서부터 계산을 더하는 식이지만, 앞에서부터 생각해도 결과는 같다는 걸 알 수 있다. 무슨 말이냐면, 앞의 도시부터 기름을 사나가는데, 지금 내가 있는 도시보다 싼도시가 나올때까지 현재 도시의 가격으로 기름을 사나가는 것이다.

Code