연료 채우기 (1826번) - 백준 (BOJ)

https://www.acmicpc.net/problem/1826

1826번: 연료 채우기

 

 

백준 - 연료 채우기 (Expedition) (1700번)

 

난이도 : Gold 2

알고리즘&자료구조 : Priority Queue (우선순위 큐) & Greedy (그리디)

시간복잡도(Time Complexity) : O( N*logN )

---

< 전체 코드 >

import sys
input = sys.stdin.readline
from heapq import heappop, heappush


class Truck():
    def __init__(self, L, P):
        self.goal = L
        self.loc = P
        self.fuels = []
        self.count = 0


if __name__ == '__main__':
    N = int(input())
    stops = [(0, 0) for _ in range(N)]
    for i in range(N):
        stops[i] = tuple(map(int, input().split()))
    stops.sort(key=lambda x: x[0])
    
    truck = Truck(*map(int, input().split()))
    i = 0
    while i < N and truck.loc < truck.goal:
        while i < N and stops[i][0] <= truck.loc:
            heappush(truck.fuels, -stops[i][1])
            i += 1
        if not truck.fuels:
            break
        truck.loc -= heappop(truck.fuels)
        truck.count += 1
    while truck.fuels and truck.loc < truck.goal:
        truck.loc -= heappop(truck.fuels)
        truck.count += 1        
    print(-1 if truck.loc < truck.goal else truck.count)

---

 

★ 트럭의 현재 위치에서 방문할 수 있는 주유소 중,

연료의 양이 많은 순으로 우선적으로 방문하는 "그리디"를 활용하는 문제이다.

이 과정을 "우선순위 큐"를 활용해 더 빠르게 구현할 수 있다.

 

 

 

① 주유소들의 위치를 오름차순으로 정렬하고,

트럭이 현재 갖고있는 연료만큼 트럭을 일단 이동시킨다.

 

② 이동하면서 지나친 주유소들의 연료들을, "self.fuels" 에 넣는다. 

 

③ 후보 연료들 중, 가장 양이 많은 연료만큼 트럭을 이동시킨다. ( Greedy )

이것은 주유소를 한 번 방문한 것과 같으므로, "self.count" 에 1을 더해준다.

 

④ 위 ①~③ 작업을 트럭이 마을에 도착하거나, "self.fuels" 에 아무것도 남지 않을 때까지 반복한다.

그리고 마지막에 트럭의 위치가 마을에 도달하지 못한 상태라면 -1을,

도달했다면 현재까지 방문한 주유소 수 self.count 를 출력한다.