[백준/ 파이썬] 1826번 연료 채우기

백준 1826번 연료 채우기

백준 1826번 연료 채우기 문제입니다.
먼저 문제에 대한 이해를 간단하게 해보겠습니다. 이 문제는 현재위치에서 마을까지 가야되는데 연료가 부족하기때문에 주유소를 들려야할 경우가 발생합니다. 이때 최소한으로 주유소를 방문하면 됩니다.

이 문제는 쉽게 생각해주면 됩니다. 우리는 결국 마을에 도착하기 위해서는 중간 지점들인 주유소로 이동을 해야합니다. 그치만 해당 주유소에서 주유를 할지 하지 않을지 잘 모릅니다.
그렇다면 어떻게 해야지만 주유소에서 주유를 할 수 있는지 알 수 있을까요?
우선 현재위치에서 다음 주유소 위치로 이동할 수 없을때 문제가 발생합니다. 그렇다면 현재 위치의 주유소에서 주유를 하면 될까요? 안됩니다. 부족할수도 있습니다. 그렇게 부족하면 바로 이전의 주유소에서 또 주유를 해야할까요? 이 방법도 항상 최적의 해를 보장해주지는 못하는 것 같습니다.
결국 최적의 해를 보장하기 위해서는 우리는 지나온 주유소를 기억하는 배열을 만들어야합니다. 그래서 주유를 해야할때 지나온 주유소들중에서 가장 많이 주유할 수 있는 곳부터 주유를 한다는 생각으로 코드를 짜면 됩니다.

이 문제를 푸는데 가장 핵심적인 아이디어.

힙에다가 지나온 주유소들의 연료의 양을 기록하자. -> 힙에 저장해야 빠르게 최댓값을 찾을 수 있다.

이 생각을 바탕으로 문제를 해결하면 됩니다.

전체코드

import heapq
n = int(input())
station = []
for _ in range(n+1):
    location, gas = map(int, input().split())
    station.append([location, gas])

station.sort()
fuel = station[n][1] #처음에 가지고 있는 연료량
current_location = 0 #초기 위치
cnt = 0

h = []  #힙을 이용해 최대값을 빠르게 찾아내기.
for i in range(n+1):
    distance = station[i][0] - current_location
    current_location = station[i][0]
    if fuel < distance: #연료가 부족할때. 빌려와야하는데, 지나간 주유소들중에서 가장 연료를 많이 채울수 있는 주유소를 선택.
        while fuel < distance:
            if len(h) > 0:
                fuel += (-1*heapq.heappop(h))
                cnt += 1
            else:
                cnt = -1
                break
        if cnt == -1:
            break
    fuel -= distance
    heapq.heappush(h, -1 * station[i][1]) #일부러 -1을 곱해 최대값을 찾기 쉽게 해줬음.
print(cnt)