[BOJ] 백준 13305 주유소 (Swift)

문제

https://www.acmicpc.net/problem/13305

13305번: 주유소

풀이

이 문제는 그리디 알고리즘의 말 그대로, 현재 상황의 최적의 해를 고르는 방식으로 풀이할 수 있습니다.

이와같이 도시가 있다면, 첫번째 도시에서는 무조건 2리터는 주유를 해야합니다.
2리터를 주유를 하고 난 뒤, 두번째 도시로 가게됩니다.

첫번째 도시보다 기름 값이 더 싸기 때문에 두번째 도시에서 3리터 만큼 주유를 하고 세번째 도시로 이동합니다.

세번째 도시에서는 두번째 도시보다 기름값이 더 비쌉니다.
그렇다면 두번째 도시에서 4리터를 주유를 하고 네번째 도시까지 이동하는 것이 최소의 비용일 것입니다.

따라서, 다음 도시에 들렸을 때, 이전 도시의 비용보다 더 비싸다면 이전 도시의 기름값으로 거리만큼 주유를 해주면 최소의 비용으로 이동할 수 있습니다.

소스코드

후기

현재 상황에서 최적의 해를 고르는 방식으로, 그리디 알고리즘의 전형적인 특성을 갖는 문제인 것 같습니다.