문제
문제 해설
보내는 마을, 받는 마을, 택배 수가 정해져 있고 배송할 수 있는 최대 박스의 개수를 구하는 문제입니다.
저는 처음에 1번 마을부터 방문하여 가장 빨리 도착하는 순서대로 최대한 담았지만 다음과 같은 반례에 막혀 틀렸습니다.
n : 4
space : 20
1 4 20
2 3 20
3 4 20
1번 마을에서 4번 마을의 20개를 든다면 2번 3번 마을에서는 아무것도 들 수 없습니다.
-
각 마을에서의 트럭의 여유 공간
1 2 3 4
0 0 0 0 -
각 마을에서의 택배 픽업 수
1 2 3 4
20 0 0 0
트럭의 여유 공간을 최대한 많이 만들고, 택배 픽업 수를 가장 많이 골라야 합니다. 따라서 배달이 가장 빨리 끝나며, 그 중에서도 마을에서 픽업하는 상자가 낭비되지 않도록 [도착마을번호, 시작 마을 번호] 순으로 정렬해야합니다.
정렬 후 보내는 마을(s), 받는 마을(e), 택배 수(amount)를 뽑아
s부터 e-1까지 트럭은 amount 만큼을 들고 있다. 라는 것을 표현하기 위해 선형 리스트를 사용합니다.
풀이 코드
import sys
input = sys.stdin.readline
n, space = map(int, input().split())
m = int(input())
box = [0] * (n + 1)
send = []
answer = 0
# 1. 도착하는 마을 마다 가장 빨리 도착하는 순서부터 최대로 담는다 - 틀림
# 2. [받는 마을, 보내는 마을] 순으로 정렬한다.
for i in range(m):
a, b, amount = map(int, input().split())
send.append([a, b, amount])
send.sort(key=lambda x: (x[1], x[0]))
for start, destination, boxes in send:
maxbox = boxes
# start부터 dest까지 얼만큼 박스를 보낼 수 있는지 검사
for i in range(start, destination):
maxbox = min(maxbox, space - box[i])
# 박스를 담는 동시에 answer 또한 +, 어차피 담은 박스는 반드시 배달된다.
for i in range(start, destination):
box[i] += maxbox
answer += maxbox
print(answer)