📚 1826 - 연료 채우기

연료 채우기

이해

시작하기에 앞서 예제 입력

4
4 4
5 2
11 5
15 10
25 10

결과 : 3

2
2 3
4 7
14 4

결과 : 2

나 같은 경우, 2번째 예제를 생각하지 못해 제출하니 틀렸었다.

아직 제출하지 않았다면 추가 예제를 돌려보자!

ex)

4
4 4
5 2
11 5
15 10
25 10

일 때, 어떻게 방문한 주유소의 개수가 최소가 될까?

현재 연료 : 10
갈 수 있는 곳 1 ~ 10까지 갈 수 있다.
다만, 방문한 주유소의 개수가 최소가 되기 위해서는 우선순위 큐를 이용하면 된다.
현재 연료 크기를 대상으로 우선순위 큐에 삽입한다.

연료가 10이므로, 방문할 수 있는 주유소는 4, 5이다.
연료를 기준으로 내림차순 정렬한다.
(4, 4), (5, 2)이다.

다음 위치는 14를(10 + 4) 기준으로 확인한다.
(11, 5), (5, 2)

다음 위치는 (14 + 5) 기준으로 학인한다.
(15, 10), (5, 2)


=> 3번

이와 같은 문제는 heap을 이용하면 된다.
반복문을 이용할 때 저장공간에서 삽입 삭제가 자주 일어나고 매번 가장 큰 or 작은 데이터를 찾을 때 heapq를 이용한다.

연료 채우기 참고한 블로그

검색을 통해 알게 되었는데 이 문제는 최소힙과 최대힙 하나씩 두고 최소힙에 모든 주유소를 좌표순으로 저장하고, 최대힙에 현재 연료를 가지고 도달할 수 있는 주유소들을 모두 담는다.
그리고나서 도달할 수 있는 최대의 기름을 채울 수 있는 주유소에서 연료를 넣는 과정을 반복하면 된다.

🔔 정리
현재 기름으로 도착지에 도착할 수 있는가?

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

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

소스

import sys  
import heapq  
read = sys.stdin.readline  
  
n = int(read())  
  
gasStation = []  
  
for _ in range(n):  
    a, b = map(int, read().split())  
    heapq.heappush(gasStation, [a, b])  
  
l, p = map(int, read().split())  
  
move = []  
answer = 0  
  
while p < l:  
  
    # 주유소 정보가 있고, 주유소 위치가 연료양보다 작거나 같을 때  
    while gasStation and gasStation[0][0] <= p:  
  
        g, f = heapq.heappop(gasStation)  
        # 우선순위 큐  
        # 정렬을 할 때, 주유소에서 채울 수 있는 연료양으로 한다.  
        # heap은 오름차순으로 정렬이 되므로  
        # 연료양 * -1 을 하여, 내림차순으로 정렬을 한다.  
        heapq.heappush(move, [-1*f, g])  
  
    # 최대힙이 비었다면 도달할 수 없는 의미로 -1을 출력한다.  
    if not move:  
        answer = -1  
        break  
    else:  
        f, g = heapq.heappop(move)  
        p += -1 * f  
        # p는 연료 양을 의미한다.  
        answer += 1  
  
print(answer)