[백준] 8980번: 택배(Python)

1. 문제 링크

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

8980번: 택배

2. 풀이

1) 풀이 설명

- 빠른 도착지의 짐 부터 싣는데 최적해라는 것
- 도착지를 기준으로 s-r 까지 가장 많이 실을 수 있는 짐의 양을 재는 것이다.

• 도착지를 기준으로 오름차순으로 정렬한다.
• 시작부터 도착지 범위에서 min(남은 트럭 용량(capa), 박스 크기(box)) 을 골라서 가장 작은 값을 넣는 것이다. 
  • 이때 박스 크기는 달라지지 않지만, 범위 내에서의 택배 용량은 다 다를 수 있으므로 비교해주는 것
• 택배에 싣는 박스 크기는 각 마을의 트럭 용량에서 빼준다.

 

2) 풀이 코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())

m = int(input())
infos = []
for _ in range(m):
    s, r, box = map(int, input().split())
    infos.append((s, r, box))

capa = [C] * (N+1) # 각 마을 별 남은 트럭 용량

total = 0
infos.sort(key=lambda x: x[1])

for s, r, box in infos:
    min_value = C

    for i in range(s, r):# box 크기는 변하지 않지만, 범위 내에 트럭 용량을 비교하는 것
        if min_value > min(capa[i], box):
            min_value = min(capa[i], box)

    for i in range(s, r):
        capa[i] -= min_value

    total += min_value

print(total)

 

* 풀이 참고

모르겠어서 풀이 참조함 ㅠ [출처]: https://ddiyeon.tistory.com/36