[baekjoon] 백준 1826번(파이썬): 연료 채우기

문제

1826번: 연료 채우기

- 성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다.

- 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다.

- 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다.

- 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다.

- 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화하려 한다.

- 그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다.

- 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 문제이다.

- 정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다.

- 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

- 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 주유소의 정보가 주어진다.

- 주유소의 정보는 두 개의 정수 a, b로 이루어져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다.

- 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

- 만약 마을에 도착하지 못할경우 -1을 출력한다.

알고리즘

- 주유소의 개수를 입력받는다.

- 힙 푸시를 통해 주유소의 정보를 입력받아 리스트에 넣는다.

- 현재 있는 연료로 마을까지 갈 수 있을 때까지 반복한다.

- 앞으로 주유소가 있고 다음 주유소를 현재 연료로 갈 수 있으면 반복한다.

- 주유소의 연료양 기준으로 최대힙을 만들어 리스트에 푸시한다. 현재 연료로 갈 수 있는 모든 주유소중에 제일 많은 연료를 충전해주는 것을 구하기 위해서이다.

- 최대힙이 없으면 현재 연료로 다음 주유소까지 갈 수 없는 것으로 -1을 출력한다.

- 최대힙을 팝 하여 그때의 연료를 충전하고 카운트한다.

코드

import sys
import heapq

n = int(sys.stdin.readline())
ab = []
[heapq.heappush(ab, list(map(int, sys.stdin.readline().split()))) for _ in range(n)]
l, p = map(int, sys.stdin.readline().split())
cnt = 0
heap = []

# 현재 있는 연료로 마을까지 갈수 있을 때까지 반복
while p < l:

    # 앞으로 주유소가 있고 다음 주유소를 현재 연료로 갈 수 있으면 
    # 현재 연료로 갈 수 있는 모든 주유소를 확인
    while ab and ab[0][0] <= p:
        # 주유소의 연료양 기준으로 최대힙을 만들어 리스트에 푸시한다.
        a, b = heapq.heappop(ab)
        heapq.heappush(heap, [-b, a])

    # 현재 연료로 다음 주유소까지 갈 수 없으므로 -1 출력
    if not heap:
        cnt = -1
        break

    # 최대힙을 팝한다.(연료를 제일 많이 충전해주는 주유소)
    b, a = heapq.heappop(heap)
    # 연료를 충전한다.
    p += -b
    cnt += 1

print(cnt)

github

junjange/CodingTest