[백준] 1826번 : 연료 채우기

1826번: 연료 채우기

1826번: 연료 채우기

🤔 문제분석

데이터를 거리는 오름차순 기름은 내림차순으로 정렬하고, 데이터를 순회하면서 우선순위큐를 활용하여 문제를 해결하였습니다.

배열을 순회하면서 우선순위큐에 기름을 가장 많이 넣을 수 있는 주유소를 넣습니다. 그리고 탱크의 오일이 다 바닥날 수 있는 거리에 도달하면 우선순위 큐에서 기름을 가장 많이 넣을 수 있는 주유소에서 기름을 넣습니다. 여기서 중요한점은 단 한번을 넣을 수 있는게 아니라, 여러번 넣을 수 있다는 점을 고려해야합니다.

예를들어 현재 기름은 10, 거리는 20이라고 했을때 지금까지 방문한 주유소가 (6, 4, 3, 2) 라고 한다면 6과 4를 빼내어서 현재 기름에 충전을 해야 다음거리가 20인 곳에 도달 할 수 있게됩니다.

💻 코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())

oil_station = []

for _ in range(N):
    a, b = map(int, input().split())
    oil_station.append((a, b))
    
oil_station.sort(key=lambda x:(x[0], -x[1]))

queue = []
cnt = 0
L, P = map(int, input().split())
oil_station.append((L, 0))

for next, oil in oil_station:
    if P >= L:
        break
    
    while next > P and queue:
        P += -heapq.heappop(queue)
        cnt += 1
    
    if next > P:
        break
    
    heapq.heappush(queue, -oil)

print(cnt if P >= L else -1)

🎯 피드백 및 개선사항

해당 문제를 풀때 처음에 이분탐색으로 문제를 해결하였는데, 기름을 한번넣고 거리가 부족하여 다음거리를 이동 할 수 없는 점을 고려하지 못하여 문제를 해결하지 못하였습니다. 그래서 이분탐색으로는 풀기 어렵다는 결론이 나왔고 우선순위큐를 활용하여 문제를 해결하였습니다.