백준 13305번 주유소 - Python

https://www.acmicpc.net/problem/13305

문제 해설

각 도시를 이동해야 하는데 도시를 이동할 때는 주유를 해야만 이동할 수 있다.

예제 입력 1번의 경우 첫 도시(5)에서 다음 도시(2)로 2km를 이동해야하는데 처음에는 주유가 되어 있지 않아서 리터당(5)의 가격에 2리터를 충전해야 다음 도시(2)로 이동할 수 있다.

이렇게 해당 도시에 도착할 때 마다 다음 도시거리만큼 주유한다고 가정했을때는

(5*2) + (2*3) + (4*1) = 20의 비용이 들게 된다. 그러나 꼭 도시에 도착할 때 마다 주유할 필요는 없고 한 도시에서 주유를 무한히 할 수 있기 때문에 가격이 싼 도시에서 주유를 최대한 많이 해놓는게 이 문제의 포인트이다.

(5*2) + (2*4) = 18 이 처럼 두번째 도시에서 4리터를 충전해 놓으면 18의 비용으로 모든 도시를 이동할 수 있다.

해결 방법

각 도시의 주유비용이 최소인지 판단하여 최소라면 해당 비용으로 최소값을 변경해주고 아니라면 기존 최소값으로 주유를 하면 된다.

코드

import sys

input = sys.stdin.readline

n = int(input())
dis = list(map(int, input().split()))
price = list(map(int, input().split()))

MIN = price[0]
money = 0

for i in range(len(dis)):
    if MIN > price[i]:
        MIN = price[i]
    
    money += MIN * dis[i]
print(money)