[Python] Baekjoon - 13305. 주유소

백준 13305번 주유소 문제는 N개의 도시를 이동하는 동안 필요한 최소 주유비를 구하는 문제다. 가격이 저렴한 주유소에서 최대한 많이 주유하고 가야 하는 문제인데, 그리디 알고리즘을 사용해서 해결할 수 있다. 난이도는 실버 4이다.

 

백준 13305번 주유소 문제 정보

알고리즘 분류

- 그리디 알고리즘

난이도

- 실버 4

 

주유소 문제 요약

N개의 도시가 한 줄로 연결되어 있으며 각 도시 사이의 거리와 각 도시의 기름값이 주어질 때, 맨 왼쪽 도시에서 맨 오른쪽 도시까지 가기 위한 최소 주유비를 구하는 문제다.

 

문제 풀이 과정

가격이 저렴한 주유소에서 최대한 많이 주유하고 가야 한다. 따라서 왼쪽부터 도시를 하나씩 이동하면서 현재까지 기름값이 가장 싼 금액을 곱해가면 된다.

 

코드

import sys

def get_min_pay():
    global N, price, dist

    total_cost = 0
    minist = price[0]
    for idx, p in enumerate(price[:-1]):
        minist = min(minist, p)
        total_cost += minist * dist[idx]
    return total_cost


if __name__ == '__main__':
    N = int(input())
    dist = list(map(int, sys.stdin.readline().split()))
    price = list(map(int, sys.stdin.readline().split()))

    print(get_min_pay())