[BOJ] 13305: 주유소

 

BOJ 13305: 주유소

 

❓문제 설명

n개의 지역을 일렬로 지나는데 필요한 가장 최소의 기름값을 구하는 문제이다.

지역 간 거리와 각 지역에서의 기름값이 각각 리스트로 주어진다.

시작 시점엔 기름이 존재하지 않고,

기름은 무제한으로 담긴다 가정하에

가장 최소의 비용을 써서 마지막 지역까지 도달하면 된다.

❗️문제 풀이

시작 시점엔 기름이 있지 않기 때문에, 두 번째 지역으로 가기 위한 최소한의 기름을 넣어야 한다.

더불어, 주어진 리스트를 정렬하면 안되기에 최소 거리당 주유 금액을 저장하는 변수를 설정했다.

import sys
N = int(sys.stdin.readline())
length_list = list(map(int, sys.stdin.readline().split()))
price_list = list(map(int, sys.stdin.readline().split()))

# 총 주유 금액
# 두 번째 지역으로 가기 위해 최소한의 기름만 충전함.
gas_price = price_list[0] * length_list[0]

# 최소 거리 당 주유 금액
min_unit_price = price_list[0]

 

이 거리당 최소 주유 금액 (min_unit_price)를 매 지역마다 갱신하며 주유 금액의 최솟값을 구하면 된다.

for i in range(1, len(price_list) - 1):
    if(price_list[i] <= price_list[i - 1]):
        min_unit_price = min(price_list[i], min_unit_price)
        gas_price += min_unit_price * length_list[i]

    else: # price_list[i] > price_list[i - 1]
        min_unit_price = min(min_unit_price, price_list[i - 1])
        gas_price += min_unit_price * length_list[i]


print(gas_price)

첫 번째 지점에서 필수로 주유해야 하는 금액을 미리 저장했고, 마지막 지점의 주유 금액은 필요하지 않으므로

반복문을 1 ~ len(price_list) - 1 까지만 진행했다.

 

i번째 가격이 i-1번째 가격보다 작거나 같은 경우 / i번째 가격이 i-1번째 가격보다 큰 경우

두 가지로 나눠 최소 거리 당 주유 금액을 갱신했고,

총 주유 금액에 i번째 거리 * 최소 금액 을 더해가며 최소 주유 금액을 구할 수 있었다.

 

 📌 전체 코드

import sys

N = int(sys.stdin.readline())
length_list = list(map(int, sys.stdin.readline().split()))
price_list = list(map(int, sys.stdin.readline().split()))

gas_price = price_list[0] * length_list[0]
min_unit_price = price_list[0]

for i in range(1, len(price_list) - 1):
    if(price_list[i] <= price_list[i - 1]):
        min_unit_price = min(price_list[i], min_unit_price)
        gas_price += min_unit_price * length_list[i]
    else:
        min_unit_price = min(min_unit_price, price_list[i - 1])
        gas_price += min_unit_price * length_list[i]

print(gas_price)