1826. 연료 채우기 (Python)

1826번: 연료 채우기

 

풀이

 현재 연료의 양으로 갈 수 있는 거리를 간 후 방문할 수 있었던 주유소 중 가장 연료를 많이 채울 수 있는 주유소에 들렀다고 가정하고 해당 연료를 트럭에 추가해준다. 추가해준 연료의 양만큼 이동하고 방문할 수 있게 된 주유소를 추가로 탐색한다. 그 후 가장 연료를 많이 채울 수 있는 주유소에 들렀다고 가정하고 해당 연료를 트럭에 추가하는 과정을 반복하면 된다.

 

 문제에 나와있는 예제는 다음과 같다.

 

 처음 트럭이 갖고 있는 연료의 양은 10이므로 일단 트럭이 10에 위치하고 있다고 가정하자.

 

 트럭은 10까지 오는 중에 4와 5에 있는 주유소에서 멈출 수 있었다. 4와 5에서 채울 수 있는 연료인 4와 2를 최대힙에 넣는다. 그 후 최대힙에서 값을 꺼내어 현재 위치에 더해준다. 현재 트럭은 10에서 4만큼 추가로 이동하여 14에 위치하게 된다.

 

 트럭이 10에서 14로 이동하면서 11에 있는 주유소를 지나쳤다. 11에 있는 주유소의 채울 수 있는 연료인 5를 최대힙에 넣는다. 그 후 최대힙에서 값을 꺼내어 현재 위치에 더해준다. 현재 트럭은 14에서 5만큼 추가로 이동하여 19에 위치하게 된다.

 

 트럭이 14에서 19로 이동하며 15에 있는 주유소를 지나쳤다. 15 위치의 주유소의 채울 수 있는 연료인 10을 최대힙에 넣는다. 그 후 최대힙에서 값을 꺼내어 현재 위치에 더해준다. 현재 트럭은 19에서 10만큼 추가로 이동하여 29에 위치하게 된다.

 

 이를 통해 총 3번 주유소에서 멈추면 마을에 도착할 수 있음을 구할 수 있다.

 

 

 코드

import sys
import heapq 
input = sys.stdin.readline 

if __name__ == '__main__':
    N = int(input()) # 주유소의 개수
    gasStation = [] # 주유소 정보 (주유소 위치, 채울 수 있는 연료의 양)
    q = []  # 현재 트럭의 위치를 기준으로 지나쳤던 주유소들의 연료의 양을 담아두는 최대 힙 

    for _ in range(N):
        a, b = map(int, input().split())
        gasStation.append((a, b))
    gasStation.sort(key=lambda x: x[0]) # 위치를 기준으로 정렬한다.

    destination, gas = map(int, input().split()) # 마을 위치, 트럭에 원래 있던 연료의 양(트럭의 위치라고 생각하자)
    idx = 0 # gasStation 배열의 인덱스 번호
    res = 0 # 트럭이 주유소에서 멈추는 횟수

    while True:
        # 현재 트럭이 마을에 도착했거나 주유소 정보를 다 살펴봤을 경우 while문 종료 
        if gas >= destination or idx == len(gasStation):
            break 
        
        # 아직 살펴볼 주유소 정보가 남아있고 현재 살펴볼 주유소의 위치가 현재 트럭의 위치 이전에 있을 경우
        # 최대 힙에 해당 주유소의 연료의 양을 넣어주고 idx를 1 증가시킨다.
        while idx < len(gasStation) and gasStation[idx][0] <= gas:
            heapq.heappush(q, -gasStation[idx][1])
            idx += 1 

        # 최대힙에 값이 있을 경우 값을 하나 꺼내어 현재 위치를 그만큼 이동시킨다.
        # 최대힙에 값이 없을 경우 트럭이 멈출 수 있는 주유소가 없다는 뜻이므로 while문을 종료시킨다.
        if q:
            gas += -heapq.heappop(q)
            res += 1
        else:
            break 
    
    # 위의 while문이 종료되고 아직 최대힙에 값이 남아있다면 
    # 트럭이 마을에 도착할 때까지 값을 꺼내어 트럭을 이동시킨다.
    while q:
        if gas >= destination:
            break 

        gas += -heapq.heappop(q)
        res += 1 
    
    # 위의 과정을 끝냈을 때 트럭이 마을에 도착했다면 res를 출력하고 
    # 마을에 도착하지 못했다면 -1을 출력한다.
    if gas >= destination:
        print(res)
    else:
        print(-1)