[Python] 주유소 - 백준 (그리디)

해당 글은 백준 13305번 문제 '주유소'를 다룬다.

문제

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

13305번: 주유소

 

설명

처음엔 어렵게 생각했는데, 생각보다 간단하게 풀 수 있는 그리디 문제였다.

도시를 이동할 때, 가격의 최솟값을 저장해두고 현재 도시의 가격이 그 값보다 작다면 최솟값을 업데이트 해준다.

그리고 계속해서 가격의 최솟값과 이동할 도시의 길이를 곱한 모든 합이 최종 출력값이다.

 

코드

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

min_price = price[0]
result = 0
for i in range(n-1):
    if min_price > price[i]:
        min_price = price[i]
    result += min_price*city_length[i]
print(result)