문제링크 : https://www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
작성코드
해설
가장 싼 기름을 최대한 많이 사용해야만 최소비용으로 도착할 수 있다
하지만 해당 기름은 도착 이후부터 사용할 수 있기 때문에 미리 list를 돌면서 탐색이 아닌
도시를 지나며 최소값 갱신을 통해 판단한다.
현재까지 도착한 도시 중 가장 싼 기름을 사용하여 다음 목적지 까지 도달하는 비용을 계산한다.
단, 이때 마지막 도시의 다음 목적지는 없으므로 distance[N]의 값은 존재하지 않는다.
for 문에서의 계산 편의성을 위해 다음 목적지 까지의 거리를 0으로 지정해주면 된다.
'백준 > Python' 카테고리의 다른 글
| [백준] 27160 할리갈리 (python 파이썬) (0) | 2023.01.15 |
|---|---|
| [백준] 27159 노 땡스! (python 파이썬) (0) | 2023.01.15 |
| [백준] 1541 잃어버린 괄호 (python 파이썬) (0) | 2023.01.12 |
| [백준] 11399 ATM (python 파이썬) (0) | 2023.01.11 |
| [백준] 1931 회의실 배정 (python 파이썬) (0) | 2023.01.10 |