악곱 == 악성곱슬

그리디 알고리즘

---

내가 생각하는 해당 문제의 그리디 정당성은 다음과 같다

• 주유소에서 넣을 수 있는 기름의 양이 제한되어 있지 않다
• 뒤 주유소의 가격에 의해 앞에서의 결과가 달라지지 않는다 → 리터당 가격 * 다음 주유소까지의 거리 만 신경 쓰면 된다는 점
• 뒤 주유소가 더 비싸다면, 앞 주유소의 가격대로 계산하면 된다.

import sys
N = int(sys.stdin.readline())
length = list(map(int, sys.stdin.readline().split()))  # N-1 개
cost = list(map(int, sys.stdin.readline().split()))    # N 개
tmp = cost[0]
answer = 0
for i in range(N-1):
    if cost[i] < tmp:   # 현재 가격이 싸면
        tmp = cost[i]   # 해당 가격으로 업데이트
    answer += (tmp * length[i])
print(answer)