[백준 알고리즘] - 주유소 (13305번) with Python

📎 간략한 문제 정리

• 

  각 지역은 주유소를 가지고 있고, 주유소마다 기름의 가격은 다릅니다. 위의 그림에서는 각 지역마다 기름 가격이 5, 2, 4, 1원이고 지역간 이동시 필요간 기름의 양이 2, 3, 1 리터입니다. 왼쪽 시작점에서 오른쪽 도착점까지 이동하는데 필요한 기름의 최소 비용을 구하는 문제입니다.

📈 문제 분석

• 기름통의 크기가 한정되어있다면 조금 어려운 문제일 수 있겠지만 각 지역에서 기름을 무제한으로 구매 가능하므로 구매 조건만 생각하면 될 문제입니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 시작점에서 다음 지역의 기름값을 보고 만약 현재 위치 가격이 더 높다면 다음 지역 이동까지 필요한 만큼의 기름만 구매하고 넘어갑니다. 하지만 지금 지역의 기름가격이 더 낮다면 다다음 지역까지 거리만큼 기름을 구매하고 종료지점 도착까지 반복하여 다시 비교합니다. 카테고리는 그리디 알고리즘이지만 실제로는 시뮬레이션에 가까웠습니다.

💻 풀이한 코드

from sys import stdin
input = stdin.readline
N = int(input())
gas_to_move = list(map(int, input().split()))
gas_price = list(map(int, input().split()))
cost = 0
current_price = gas_price[0]
temp_distance = gas_to_move[0]
for i in range(1, N):
    if i == N-1:
        cost += current_price * temp_distance
        break
    if current_price > gas_price[i]:
        cost += current_price * temp_distance
        current_price = gas_price[i]
        temp_distance = gas_to_move[i]
    else:
        temp_distance += gas_to_move[i]
print(cost)

📝 해결 과정에서 만난 문제, 고민들

• 로직 자체는 매우 간단했지만 엣지 포인트를 어떻게 처리할지가 중요했습니다.
• 🧐 만약 이 문제를 각 지역마다 살 수 있는 기름의 상한선이 있다면? : 상한선이 있다면 복잡해질 것 같지만 실제로는 조건 하나가 추가될 뿐입니다. 위의 else 구문에서 상한을 넘는지 확인하면 될 것 같습니다. 다만, 상한선이 있다면 일부만 살 수 있는 경우가 발생할 수 있습니다. 예를 들어 10리터의 한도가 있는 상황에서 현재 8리터를 구매한 상황이고, 다음 이동을 위해서는 4리터가 필요할 때 2리터는 현재 위치에서 추가로 구매하고 나머지 2리터를 다음 지역에서 무조건 사는 로직이 필요합니다. 이러한 문제 역시 시뮬레이션에 가까운 개념입니다.

https://www.acmicpc.net/problem/13305