[백준] 13305 주유소 (python 파이썬)

백준/Python

노랑꼬리 2023. 1. 13. 09:18

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

가장 싼 기름을 최대한 많이 사용해야만 최소비용으로 도착할 수 있다

하지만 해당 기름은 도착 이후부터 사용할 수 있기 때문에 미리 list를 돌면서 탐색이 아닌

도시를 지나며 최소값 갱신을 통해 판단한다.

현재까지 도착한 도시 중 가장 싼 기름을 사용하여 다음 목적지 까지 도달하는 비용을 계산한다.

단, 이때 마지막 도시의 다음 목적지는 없으므로 distance[N]의 값은 존재하지 않는다.

for 문에서의 계산 편의성을 위해 다음 목적지 까지의 거리를 0으로 지정해주면 된다.