[백준1826번] 연료 채우기 / Python3

문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

입력

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

예제 입력 1

4
4 4
5 2
11 5
15 10
25 10

예제 출력 1

3

나의 풀이

처음 접근을 현재 좌표를 기준으로 도달할 수 있는 기준으로 최대힙에 넣고 가장 멀리 온 좌표를 꺼내가면서 풀어보았다. 주어진 테스트 케이스는 맞았지만 AC하지는 못했었다. 따라서 검색을 해보니 최소힙과 최대힙 하나씩 두고 최소힙에 모든 주유소를 좌표순으로 저장하고, 최대힙에 현재 연료를 가지고 도달할 수 있는 주유소들을 모두 담았다. 그리고나서 도달할 수 있는 최대의 기름을 채울 수 있는 주유소에서 연료를 넣고 해당 과정을 반복하였다.

위의 과정을 보기 좋게 정리해보면 다음과 같다.

• 현재 기름으로 도착지에 도착할 수 있는가?
  • 있다면 : break
  • 없다면
    • 최소힙에서 주유소를 하나씩 꺼내며 현재 연료로 도달할 수 있는지 확인
      • 위의 과정을 반복하며 도달 가능한 모든 주유소를 최대힙에 push (연료를 기준으로)
    • 만약 최대힙이 비었다면 도달할 수 없다는 의미로 -1 출력
    • 최대힙에서 도달할 수 있으면서 연료가 최대인 주유소를 하나 pop하여 현재 연료에 더하고 카운트를 1증가시킨다.

상기 과정을 반복하면 도착지까지 들르는 주유소의 개수가 된다.

코드

# 1826번 연료 채우기
import heapq

n = int(input())

gas_q = []
for _ in range(n):
    heapq.heappush(gas_q, list(map(int,input().split())))
target, fuel = map(int, input().split())

move = []
cnt = 0
while fuel < target:
    while gas_q and gas_q[0][0] <= fuel:
        gs, f = heapq.heappop(gas_q)
        heapq.heappush(move, [-1 * f, gs])

    if not move:
        cnt = -1
        break

    f, gs = heapq.heappop(move)
    fuel += -1 * f
    cnt += 1  

print(cnt)