[백준 8980번] 택배 (Python)

import sys
from heapq import *
input = sys.stdin.readline

N,C = map(int,input().split())
box = [[*map(int,input().split())] for i in range(int(input()))]
send = [[] for i in range(N+1)]
receive = [0]*(N+1)
for i,j,v in box:
  send[i].append((j,v))
hq = []; result = c = 0
for i in range(N+1):
  for j,v in send[i]:
    c += v
    receive[j] += v
    heappush(hq,(-j,v))
  result += receive[i]
  c -= receive[i]
  while c>C:
    j,v = heappop(hq)
    if v>c-C:
      receive[-j] -= c-C
      heappush(hq,(j,v-c+C))
      c = C
    else:
      receive[-j] -= v
      c -= v
print(result)

우선순위 큐를 이용한 간단한 그리디 알고리즘 문제이다.

핵심 아이디어는 일단 트럭에 순서대로 모든 박스를 다 싣고, 트럭의 용량이 가득 차면 가장 멀리 배달해야하는 택배부터 버리면 된다.

 

풀이를 설명하면,

1. send에는 각 출발지점에서 배달해야하는 물량과 도착지점을 저장하고, receive에는 각 지점에 몇 개의 택배를 배달해야하는지를 저장한다.

2. 1번 지점부터 순회하면서 모든 박스를 싣는다. 박스를 heapq에도 도착지점을 음수로 해서 저장한다.

3. 현재 트럭의 용량이 가득 차있을 경우 heapq에서 박스의 용량이 넘치지 않을때까지 가장 멀리 배달해야하는 택배부터 버린다.

4. 배달 완료한 용량을 출력한다.