[백준] 13305 주유소

문제

• N개의 도시가 길이가 서로 다른 일직선 도로 위에 있을 때, 제일 왼쪽 도시에서 오른쪽 도시로 이동하는 최소 비용 계산하기
• 1km 이동하는데 1리터의 기름이 필요하다.
• 각 도시마다 주유소가 있고 주유소의 리터당 가격은 다를 수 있다.
• 기름통의 크기는 무제한이다.

 

• 2 <= N <= 100,000
• 1 <= 거리, 가격 <= 1,000,000,000

 

풀이

• 출발 도시부터 시작해 가장 저렴한 가격을 기억해두면서 그 다음 도시까지 필요한 기름을 채운다.

 

import sys
input = sys.stdin.readline

N = int(input())
roads = list(map(int, input().split()))
price = list(map(int, input().split()))

answer = 0
prev = 1e9
for i in range(N-1) :
    if price[i] < prev :
        prev = price[i]
    answer += roads[i] * prev

print(answer)

 

References

• 백준 그리디