알고리즘/BOJ
[Python] 백준 1826: 연료채우기
PIAI
2021. 9. 14. 17:54
1826번: 연료 채우기
첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경
www.acmicpc.net
1. 거리순으로 정렬을 해준다.
2. 마을에 도착할때마다 연료를 최대힙으로 넣어준다.
3. 마을에 도착할때 연료가 부족하면 힙에 있는 연료를 높은순으로 넣어준다.
4. 힙의 길이가 0 이고 연료가 부족하면 -1을 출력한다.
import sys
import heapq
n = int(input())
info = [list(map(int, input().split())) for _ in range(n)]
arrive, fuel = map(int, input().split())
ans = 0
info.append([arrive, 0])
info.sort()
heap = []
for i in range(len(info)):
if fuel - info[i][0] < 0:
while heap:
fuel += -heapq.heappop(heap)
ans += 1
if fuel - info[i][0] >= 0:
break
if len(heap) == 0 and fuel - info[i][0] < 0:
ans = -1
break
else:
heapq.heappush(heap, -info[i][1])
print(ans)