[백준]8980 택배

✔️ 문제 링크

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

💡 핵심 아이디어

1️⃣ 받는 마을 순으로 오름차순(1번 마을부터 가까운 마을부터 박스를 옮겨나름)

2️⃣ 보내는 마을과 받는 마을을 고려하여 현재 마을에서 얼마만큼의 박스를 담고 있는지 정보를 갱신하며 담을 수 있으면 박스를 담고 답을 갱신해 나감

⭐️ 소스 코드

if __name__ == '__main__':
    N, C = map(int,input().split()) # 마을 수, 트럭의 용량
    M = int(input())

    box_info = []
    load_info = []

    for _ in range(N):
        load_info.append(C)

    for _ in range(M):
        a, b, c = map(int, input().split())
        box_info.append([a,b,c])

    # 도착지 - 출발지
    box_info = sorted(box_info, key = lambda x: (x[1],x[0]))

    ans = 0

    for i in range(len(box_info)):
        start, end, storage = box_info[i]
        start -= 1
        end -= 1

        # 출발지에서 도착지까지
        min_num = min(load_info[start:end])

        if storage < min_num:
            for j in range(start, end):
                load_info[j] -= storage
            ans += storage
        else:
            for j in range(start, end):
                load_info[j] -= min_num
            ans += min_num

    print(ans)