[Python/파이썬] - 백준(BOJ) 1826번 : 연료 채우기

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

1826번: 연료 채우기

 

우선순위 큐를 이용하는 그리디 문제.

주유소를 가까운 거리가 앞으로 가도록 소팅한다.

이후 현재 위치에서 남아있는 연료를 더해 최대한 갈 수 있는 지점을 설정한다.

최대한 갈 수 있는 지점까지 맥스 힙에 heappush하고 heappop을 이용하여 가능한 주유소 중 가장 연료가 많은 주유소에 들른다.

들른 주유소까지의 거리만큼 연료를 빼고 주유소에 저장된 연료를 더한다.

이후 맥스 힙은 유지하며 최대한 갈 수 있는 지점을 변경하며 heappush, heappop 사이클을 반복한다.

목표 지점에 도달하지 않았는데 heappop이 불가능하면 -1을 출력한다.

 

import sys
from heapq import heappop, heappush
input = sys.stdin.readline


n = int(input())
arr = sorted([list(map(int,input().split())) for _ in range(n)])
end, stock = map(int,input().split())
start = 0
l = 0
answer = 0
heap = []
while start+stock < end:
    for i in range(l, len(arr)):
        if arr[i][0] > start + stock:
            break
        l = i+1
        heappush(heap, [-arr[i][1]] + arr[i])
    if not heap and start+stock < end:
        answer = -1
        break
    next = heappop(heap)
    stock += start - next[1] + next[2]
    start = next[1]
    answer += 1
print(answer)