[BOJ 1826] 연료채우기

문제

[BOJ 1826] 연료 채우기

1km 가는데 1L의 연료가 새어 나가는 상황
정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있음
마을에 도착할 때까지 주유소에서 멈추는 횟수 구하기(최대한 적은 횟수여야함)

풀이

주유소 지날 때마다

현재 도달 가능한 주유소이면 그냥 최대힙에 넣기
remain<0이라는 건 현재 주유소는 연료가 모자라 도달할 수 없다는 것이므로 이전 주유소에서 기름을 충전하고 와야 한다. (이전 주유소 중 연료가 가장 많은 주유소 선택)

마을까지의 거리는 L로 고정되어 있으므로 가장 마을과 가까운 주유소를 고르는 건 의미x
무조건 연료양이 많은 주유소를 선택해야 멈추는 횟수를 최소화할 수 있음

코드

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

N = int(input()) #  주유소의 개수 N(1 ≤ N ≤ 10,000)
stations = []
for _ in range(N):
    a,b = map(int,input().split()) # 1 ≤ 시작 위치~주유소 거리 ≤ 1,000,000, 1 ≤ 주유소에서 채울수있는 연료의 양 ≤ 100
    stations.append((a,b))
stations.sort()
L,P = map(int,input().split()) # 1 ≤ 성경~마을 거리 ≤ 1,000,000, 1 ≤ 트럭에있던 연료의 양 ≤ 100
stations.append((L,0))

pos = 0
remain = P
reserve = []
ans = 0
'''
# 주유소 지날 때마다 reserve 힙에 넣기
# remain<0이면 (과거 주유소에서) 기름 충전하기
'''
for (dist,fuel) in stations: #노트1
    remain -= dist-pos
    while remain<0:
        if not reserve: print(-1); exit(0)
        remain += -heappop(reserve)
        ans += 1
    heappush(reserve, -fuel) # 현재 도달 가능한 주유소를 힙에 넣음
    pos = dist
print(ans)

노트

모든 주유소를 끝까지 조사