문제
https://www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
아이디어
- 현재 주유소의 다음 주유소의 가격보다 싸다면 현재 주유소에서 주유를 한다.
- 다음 주유소뿐만 아니라 그 다음의 주유소도 똑같이 확인한다.
코드
https://github.com/tooha289/Algorithm/blob/main/Baekjoon/S3_%EC%A3%BC%EC%9C%A0%EC%86%8C.py
개선
for 문을 돌면서 지역적인 최소 가격을 찾고 해당 가격과 거리를 곱해서 총 가격을 계산하는 방식을 사용할 수 있다.