백준(BaekJoon) 13305번 : 주유소 - python 풀이

❓13305번 : 주유소

📈 문제 요약

N개의 도시에 있는 주유소의 기름 가격이 다르고 1리터에 거리 1을 갈 수 있다고 할 때 각 도시 사이의 거리가 주어지는 경우 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 계산하면 되는 문제

🤨 접근법

전체 가격을 낮추기 위해 특정 상황에서의 최선의 선택은 지금까지 온 주유소의 기름 값중 가장 싼 기름 값으로 다음 도시까지 이동하는 것이다. 즉, 현재 도시의 기름 가격보다 이전 도시의 기름 가격이 더 싼 경우 현재 도시에서 다음 도시까지 이동하는 기름까지 이전 도시에서 주유하고 오면 베스트이다.

이를 위해 지금까지 지나온 도시의 기름 값 중 가장 최소의 값을 관리한다. 이 값을 before_price라고 할 때 before_price가 다음 도시의 기름값보다 저렴할 경우 다음 도시까지의 거리를 특정 변수(distance)에 합산한다.

다음 도시의 기름값이 더 저렴한 경우 다음 도시까지의 거리를 합산하고, 지금까지 합산한 거리 * before_price를 결과에 한 번에 합산하고, before_price를 해당 도시의 기름값으로 업데이트 해준다.

이렇게 하면 지나온 도시 중 가장 저렴한 기름 값의 도시에서 더 저렴한 기름 값의 도시가 나올 때까지의 거리만큼 모두 주유하도록 할 수 있다. 당연한 말이지만 다음 도시의 기름 값을 미리 알 때에만 유효한 방법이다!

🔡 코드

import sys

input = sys.stdin.readline

N = int(input())
roads = list(map(int, input().rstrip().split()))
oil_prices = list(map(int, input().rstrip().split()))
before_price = oil_prices[0]
distance_using_before_oil_price = 0
result = 0

for city_idx in range(1, N):
    if before_price < oil_prices[city_idx]:
        distance_using_before_oil_price += roads[city_idx-1]
    else:
        distance_using_before_oil_price += roads[city_idx - 1]
        result += before_price * distance_using_before_oil_price

        distance_using_before_oil_price = 0
        before_price = oil_prices[city_idx]

result += distance_using_before_oil_price*before_price

print(result)

아래 코드는 위 과정을 더욱 간결하게 작성한 코드이다. 결국 요점은 새로 등장한 도시의 기름 값이 더 저렴한 경우에만 기름값을 업데이트하는 것이므로 더 저렴한 값이 나오지 않으면 매 반복마다 지나온 길과 현재 가장 저렴한 도시의 기름값으로 계산 후 더해준다.

n = int(input())
roads = list(map(int, input().split()))
oil_prices= list(map(int, input().split()))

res = 0
m = oil_prices[0]
for i in range(n-1):
	if oil_prices[i] < m:
		before_price = oil_prices[i]
	res += before_price * roads[i]