📚 8980 - 택배

택배

이해

(1) 받는 마을 순으로 정렬을 한다.
(2) 트럭 용량를 마을 개수만큼 인덱스를 가진 배열에 각각 저장한다.

• ex) 트럭의 용량이 40개면, arr[1] = 40, arr[2] = 40, arr[3] = 40 ~

(3) 트럭의 용량을 저장한 arr를 기준으로 보내는 마을에서 받는 마을 사이에서 가장 작은 값을 찾는다.

• 가장 작은 값과 트럭 용량(C)를 비교하여, 두 수 중에서 작은 값을 찾는다.

(4) 해당 구간에서 (현재 트럭 용량 - 두 수 중에서 작은 값)을 해준다.

• 트럭의 용량은(담을 수 있는 용량) 정해져 있기 때문에, 보내는 마을에서 받는 마을 사이 담을 수 있는 트럭의 용량을 정리해야 한다.
• 현재 앞에서 일부 트럭 양을 사용하였기에, 해당 구간 뒤에서도 동일하게 빼줘야 한다. (사용할 수 있는 트럭의 용량 정리)

설명이 잘되어 있는 곳

소스

import sys  
  
read = sys.stdin.readline  
  
n, c = map(int, read().split())  
m = int(read())  
  
box = []  
result = [c] * (n + 1)  
answer = 0  
  
for i in range(m):  
    a, b, c = map(int, read().split())  
    box.append([a, b, c])  
  
# (1)  
# 도착 지점을 기준으로 정렬한다.  
# 같다면, 출발 지점을 기준으로 정렬한다.  
  
box.sort(key=lambda x: (x[1], x[0]))  
  
# (2)  
# 시작지점 ~ (도착지점 - 1) 까지 중 제일 작게 남은 잔여량을 찾는다.  
# min(실은 용량, 잔여용량) 결과를 실은 박스 수에서 빼준다.  
  
for i in range(m):  
    left_idx = box[i][0]  
    right_idx = box[i][1]  
    capacity = min(result[left_idx:right_idx])  
    cur_r = min(capacity, box[i][2])  
  
    if not cur_r:  
        continue  
    else:  
        answer += cur_r  
        for j in range(left_idx, right_idx):  
            result[j] -= cur_r  
  
print(answer)

생각보다 문제 이해하는데 시간이 많이 걸렸다. 문제가 어려웠던 것 같다.