백준 - 13305 주유소

이번 문제는 주유소 문제로 각 도시마다 기름 값이 다른 주유소가 존재하고

우리는 모든 도시를 이동하기 위한 최소 비용을 구해야 한다.

 

다른건 제쳐두고 기본적인 것만 생각해보면 결국

1. 당장 다른 도시로 가기 위해서는 기름이 필요 

2. 도시를 거치며 더 싼 주유소가 나오기 전 까지는 가장 저렴한 주유소에서 왕창 주유하고 가면 된다. 

 

이러한 로직은 결국 도시를 하나씩 거치면서

이제까지 만난 기름의 최소값 만을 저장하며 순차적으로 총 가격에 더해주면 된다.

 

이러한 풀이는 그리디 알고리즘으로

현재까지 만난 주유소 중 기름 값이 가장 싼 주유소에서 주유하면 전체 주유 비용의 최소 값을 구할 수 있다는 개념이다.

 

풀이

def run():
    N = int(input())

    length_lst = list(map(int, input().split(" ")))
    price_lst = list(map(int, input().split(" ")))

    oil = price_lst[0]
    now = length_lst[0] * oil

    for i in range(1, N - 1):
        if oil > price_lst[i]:
            oil = price_lst[i]

        now += length_lst[i] * oil

    print(now)


if __name__ == "__main__":
    run()