[백준 8980] 택배 (Python)

 유형: 그리디 

 

 해결 아이디어 

- 도착이 빠른 순서대로 택배 리스트 재정렬

  : 그리디 아이디어, 1번 마을부터 출발하므로 도착이 가장 짧은 순서대로 정렬해서 순서대로 짐을 싣는다면 

   가장 짧은 기간동안 물건을 가지고 있을 수 있다.

  (처음 풀때는 (출발, 도착) 튜플을 정렬해서 출발지와 도착지가 모두 빠른 순서대로 검사해나갔지만 도착이 빠른

   순서대로 재정렬하면 됨.)

 

 구현  

- able_remain: 각 마을 번호의 위치에서 실을 수 있는 무게, 남아 있는 용량 리스트 

- 동작과정 

   (1) 도착이 빠른 주문부터 순서대로 확인하면서 from->to 경로를 지날 수 있는 남은 용량을 구한다 

   (2) 옮길 최종 무게를 결정한다 = min(지날 수 있는 남은 용량, 주문 물건의 무게)

   (3) 옮긴다. 지나오는 마을의 남은 용량을 빼준다.

 

 코드 

N, C = map(int, input().split()) #마을, 트럭용량  
M = int(input()) #보내는 박스 정보 갯수 

info_lst = [] 
for _ in range(M):
    info_lst.append(tuple(map(int, input().split())))

info_lst.sort(key=lambda x: x[1]) #도착 순서가 빠른 순서로 정렬 -> 물건을 최대한 짧게 들고 있을 수 있도록 
able_remain = [C]*(N+1) #마을 번호 1번부터 시작 

result = 0 # 총 옮긴 물건의 무게의 합 
for i in range(M):
    a, b, w = info_lst[i] #from, to 마을 번호, 옮길 물건의 무게 

    tmp = C # 옮길 물건
    # a->b 까지 옮길 수 있는 용량(남아 있는 용량)
    for j in range(a, b):
        tmp = min(tmp, able_remain[j])
    
    # 옮길 수 있는 용량 = min(옮길 수 있는 남아있는 용량, 옮길 물건의 무게)
    tmp = min(tmp, w)
    
    # 실제 물건을 옮기면서 remain 에서 물건의 무게만큼 빼주어 남은 용량을 갱신한다 
    for j in range(a, b):
        able_remain[j] -= tmp 
    
    result += tmp 

print(result)