백준 13305번: 주유소 [python]

문제 접근

가장 왼쪽에서, 가장 오른쪽으로 갈건데, 거리가 정해져있고, 기름값이 각 노드마다 정해져있다. 기름값을 최소화하되 목적지까지 갈때 드는 비용을 출력하는 문제.

가격을 최소화하기 위해, 기름값이 가장 싼 곳에서 가장 많이 구매해야한다.
가장 싼 곳에서 가야할 km만큼의 기름을 구매한다. 이를 비용에 더해주면 된다.

import sys
input = sys.stdin.readline
n = int(input()) #도시의 개수
km = list(map(int,input().split())) # 도로의 길이
price = list(map(int,input().split())) # 가격

minPrice = price[0]  # 처음엔 첫 도시의 리터당 가격을 최소값으로 설정
total = 0            # 총 비용

for i in range(n - 1):   # 마지막 도시는 목적지이므로 주유하지 않음
    if minPrice > price[i]:  # 더 싼 주유소가 나오면 갱신
        minPrice = price[i]
    total += (minPrice * km[i])  # 현재 최소 가격으로 다음 도시까지 거리만큼 주유
print(total)

현실처럼 되돌아갈 순 없지만, 미래 가격은 미리 알려주기 때문에 그리디 전략이 가능한 문제다.