[백준][13305] 주유소

• Problem Link : https://www.acmicpc.net/problem/13305

문제

• 도시의 리터당 가격과 도시 간 거리가 주어진다.
• 1리터당 1km를 갈 수 있다.
• 마지막 도시까지 최소의 비용으로 도달하려고 할 때 얼마가 필요한지 구하시오.

입력

• 첫째 줄, 도시의 개수 N이 주어진다.
• 둘째 줄, 도시 간 거리가 N-1개 주어진다.
• 셋째 줄, 도시 주유소의 리터당 가격이 N개 주어진다.

출력

• 최소 비용을 출력한다.

풀이

전형적인 그리디 알고리즘으로 가격이 낮은 주유소에서 자신보다 가격이 낮은 도시가 나올 때까지의 거리만큼 리터를 구입하면 된다. ( 1리터당 1km만큼 가므로 )

따라서 도시의 기름 가격을 이용해 지금 도시보다 가격이 낮은 도시가 나올때까지의 거리에 현재 도시의 기름 가격을 곱해서 계속 더해주기만 하면 된다.

코드

import sys

input = sys.stdin.readline

n = int(input())

line = list(map(int, input().split()))
vertex = list(map(int, input().split()))[:-1]

i = 0
ans = 0
while i < n - 1:
    ans += vertex[i] * line[i]
    j = i
    while j + 1 < n - 1 and vertex[i] <= vertex[j + 1]:
        ans += vertex[i] * line[j + 1]
        j += 1
    i = j
    i += 1

print(ans)