백준 13305 주유소 (파이썬)
접근방식
- 그리디 알고리즘으로 푸는 문제이다.
- 주유비 최소화를 위해서는 리터당 가격이 가장 적은 곳에서 주유를 하는 것이다.
- 지금까지 지난 주유소의 리터당 가격이 가장 작은 값을 변수에 저장해두었다가 가격이 더 저렴한 곳이 나왔을 경우 이 변수를 갱신한다.
파이썬 코드
import sys
n = int(sys.stdin.readline())
distances = list(map(int,sys.stdin.readline().split()))
prices = list(map(int,sys.stdin.readline().split()))
c = 0
#우선 첫번째 도시의 주유가격이 기준이 된다.
m = prices[0]
# 마지막 도시에서 주유를 할 일은 없으니 마지막에서 이전 주유소까지만 체크한다.
for i in range(n-1):
# 리터 당 금액이 더 적은 곳을 발견하였을 시 변수를 갱신한다.
if prices[i] < m:
m = prices[i]
# 드는 비용은 리터 당 금액 * 이동 거리이다
c = c + m * distances[i]
print(c)
참고
https://alpyrithm.tistory.com/134
