[Python - Greedy, Priority Queue] 1826 연료 채우기

📌 문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 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)은 성경이의 위치에서 마을까지의 거리, P(1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

저번에 풀었던 1202 보석 도둑과 비슷한 결의 문제이다. 내가 최대한 갈 수 있는 만큼 이동한 다음에, 더이상 이동할 수 없는 상황일 때, 가장 많은 연료를 넣을 수 있는 주유소에서 연료를 채우는 방식으로 이동해야 한다.

 

여기서 연료를 가장 많이 채우기 위해 우선순위 큐를 사용해서 가장 많은 연료를 갖고 있는 주유소를 찾아내야 한다.

 

도달하지 못하는 경우는, 내가 도달할 수 없는 주유소 혹은 마을까지 가지 못해서 계속해서 우선순위 큐에서 값을 뽑아내어 전진했지만, 우선순위 큐가 비어 값을 뽑아낼 수 없을 때까지 도래하게 되면 더이상 방법이 없기 때문에, 우선순위 큐가 빌 때를 실패 조건으로 해서 -1을 출력하도록 한다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())

oil = sorted(list(map(int, input().split())) for _ in range(n))

# l: 마을까지의 거리, p: 현재 연료 상태
l, p = map(int, input().split())
cnt = 0

# j = 현재 성경이의 위치
i, j = 0, 0
pq = []

while (j + p < l):
    while i < n and p >= oil[i][0] - j:
        heapq.heappush(pq, (-oil[i][1], oil[i][0]))
        i += 1
        continue

    if not pq:
        cnt = -1
        break
    else:
        resource, dist = heapq.heappop(pq)
        p -= dist + resource - j
        j = dist
        cnt += 1

print(cnt)

📄 준비

import sys
import heapq
input = sys.stdin.readline

n = int(input())

oil = sorted(list(map(int, input().split())) for _ in range(n))

# l: 마을까지의 거리, p: 현재 연료 상태
l, p = map(int, input().split())
cnt = 0

# j = 현재 성경이의 위치
i, j = 0, 0
pq = []

먼저 주유소를 정렬해주어야 한다. 거리를 오름차순으로 해서 입력이 된다는 말이 없었기 때문이다. 단골 함정이다.

 

그 이후 우선순위 큐를 사용하기 위해 pq라고 변수를 만들어줬다. i는 oil을 순회하기 위한 변수이다.

📄 풀이

while (j + p < l):
    while i < n and p >= oil[i][0] - j:
        heapq.heappush(pq, (-oil[i][1], oil[i][0]))
        i += 1
        continue

    if not pq:
        cnt = -1
        break
    else:
        resource, dist = heapq.heappop(pq)
        p -= dist + resource - j
        j = dist
        cnt += 1

print(cnt)

최대 힙을 구현할 것이기 때문에 연료의 값을 넣을 때 음수값으로 넣어준다.

 

모든 주유소를 순회하기 전, 그리고 현 위치로부터 다음 주유소까지 갈 수 있는 연료를 갖고 있는 경우에 우선순위 큐에 값을 넣어준다. 

 

만약 현재 거리에서 연료만큼 이동하여 마을까지 도달하지 못할 경우이면서 동시에, 모든 주유소를 다 순회했다거나 다음 주유소까지 갈 수 없으면 우선순위 큐에서 값을 추출한다.

 

이때, 연료를 구할 수 없는 상황에서는 -1을 출력할 수 있도록 한다. 만약 구할 수 있다면(우선순위 큐에 값이 있다면) 연료를 업데이트 해주고, 현재 위치를 갱신해주고 카운트해준다.

📌 총평

 

시간이 조금 걸렸는데 풀만 했다. 다음에는 제목에 티어도 올려볼까?