[Baekjoon]백준 13305 주유소(실버 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 최소한의 비용으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 방법을 찾아야한다

일단 제일 처음 이동할 때에는 기름이 없기 때문에 그 다음 도시로 이동할 정도의 비용은 무조건 지불해야한다

그러지 않으면 이동자체가 불가능하기 때문이다

이후에는 어떠한 방법으로 해결하였는지 서술하자면 최소한의 비용으로 가기 위해서는 특정 지점의 주유소 비용으로

더 적은 비용을 지불가능하기 전까지는 이동해야한다

result = distance[0] * cost[0]
min_cost = cost[0]

뒤의 부분에 대해 예제로 설명하자면 주유소의 가격이 2인 곳에서 1까지 이동하려면 4리터를 필요로하는데, 2원인 주유소에서 4리터를 지불하는 것이 가격이 4인 곳에서 1리터를 추가적으로 지불하는 것보다 저렴하다

식으로 계산해보면 2인 지점에서 4리터를 구입한 경우 2 * 4 = 8이 되고, 2인 지점에서 3리터를 구입하고 1리터는 4인 지점에서 구입하면 2 * 3 + 4 * 1 = 10 이 되어버리기 때문이다

이를 코드로 작성하게 된다면 첫번째 정류장의 비용을 최소 비용으로 설정한 후, 최소 비용이 갱신되기 전까지

해당 거리만큼 이동하면 된다 이후에 최소비용이 갱신되면 다시 최소비용이 나올때까지 거리를 이동하며 거리에 대한

비용을 지불하도록 코드를 작성하면 된다

for i in range(1, num-1):
    if min_cost > cost[i]:
        min_cost = cost[i]
    result += min_cost * distance[i]

이렇게 하면 최소 비용으로 제일 오른쪽 까지 이동하는 알고리즘이 완성된다

num = int(input())
distance = list(map(int, input().split()))
cost = list(map(int, input().split()))

result = distance[0] * cost[0]
min_cost = cost[0]

for i in range(1, num-1):
    if min_cost > cost[i]:
        min_cost = cost[i]
    result += min_cost * distance[i]
    
print(result)