[python/백준] 8980번: 택배

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

8980번: 택배

 

 

 

⭐ 문제

 

이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다. 

 

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

 

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

 

 

 

⭐ 코드 분석

 

 

* 빠른 도착지의 박스부터 싣는 것이 최적해 *

 

각 마을에서 실을수 있는 트럭 용량을 배열로 저장, 빠른 도착지부터 추발- 도착지사이의 택배용량 줄이기 

 

 

1. 출발지, 도착지, 박스갯수를 정하는 변수 저장, 도착지를 오름차순으로 저장

2. 각 마을에서의 트럭용량을 배열에 저장

3. 출발지, 도착지 사이 마을의 트럭 용량에서 박스 갯수 만큼 뻄

4. 지금까지 뺐던 박스 총 갯수를 반환

 

 

 

 

 

 

⭐ 코드

 

from sys import stdin
N, C = map(int, stdin.readline().split())
M = int(stdin.readline())
parcel = []
for _ in range(M):
    go, sent, box = map(int, stdin.readline().split())
    parcel.append((go, sent, box))
    parcel.sort(key=lambda x : x[1])
    
weight = [C]*N
total = 0

for go, sent, box in parcel:
    _min = C
    for i in range(go, sent):
        if _min > min(weight[i], box):
            _min = min(weight[i], box)
    for i in range(go,sent):
        weight[i] -= _min
    total += _min
print(total)