🧑‍💻/Algorithm

알고리즘) 백준 13305번 주유소 Swift

유리맥 2021. 5. 10. 19:28
반응형

www.acmicpc.net/problem/13305

 

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원 비용이 발생합니다.

풀이

 

반응형