[백준] 8980번 - 택배 (파이썬)

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

 

# 택배
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
box_num = int(input())
box_info = []
for _ in range(box_num):
    start, end, num = map(int, input().split())
    box_info.append((start, end, num))
box_info.sort(key=lambda x: (x[1]))

result = 0
arr = [W for _ in range(N+1)]
for x, y, num in box_info:
    num = min(num, min(arr[x:y]))
    if num != 0:
        for i in range(x, y):
            arr[i] -= num
        result += num

print(result)

 

그리디, 정렬
1. 박스 정보를 입력받는다. (box_info)
2. 해당 정보를 도착지점이 빠른 순서대로 정렬
3. arr : 각 마을에서 실을 수 있는 택배의 개수 (초기값 : W)
4. box_info를 탐색
    - num과 arr[x:y] 중에서 가장 작은 값을 num에 대입
    - arr[x:y]의 각 요소를 num만큼 빼주고 result += num
5. result 출력

 

출발 지점, 도착 지점이나 시작 시간, 끝나는 시간 등이 주어진 그리디 문제는

도착 지점(끝나는 시간)으로 정렬을 해서 풀어주는 것을 먼저 생각하자.

 

택배는 x마을부터 y-1마을 까지 해당 택배를 가지고 있어야 한다.

따라서 box_info를 탐색할 때, arr[x:y]에서 각각 num을 빼준다.

또한, 트럭에 최대한 탑재 가능한 택배의 개수는 W이므로 num을 해당 범위의 최솟값으로 업데이트해야 한다.