🧑💻/Algorithm
알고리즘) 백준 13305번 주유소 Swift
유리맥
2021. 5. 10. 19:28
반응형
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
예제
입력 | 출력 |
4 2 3 1 5 2 4 1 |
18 |
4 3 3 4 1 1 1 1 |
10 |
5 3 2 1 4 5 8 9 4 1 |
46 |
문제 접근
문제의 포인트는 가장 저렴한 주유소에서 충전하여 최대한 많은 거리를 가는 것입니다.
문제 속 예제를 로직화 해보았습니다.
- 0번째 : 최소 비용이 5원이므로 5원 * 2km 를 가야 합니다.
- 1번째 : 최소 비용이 5원에서 2원으로 변경됩니다. 2원 * 3km 를 갑니다.
- 2번째 : 4원보다 2원이 저렴하므로 2원 * 1km 를 갑니다.
0 ~ 2번째까지 순환문을 사용하고, 최소 리터당 가격을 저장하여 비교하여 값을 도출해 낼 수 있습니다.
결론적으로 5원 * 2km + 2원 * (3km + 1km) = 18원 비용이 발생합니다.
풀이
반응형