8980. 택배

8980번: 택배

---

 

이런 구간 류의 문제는 일단 구간의 끝을 기준으로 정렬해놓고 생각해야 한다. (참고: 20440번 문제)

왜?

보내는 마을이 빠른 택배를 먼저 실으면 어떤 일이 일어날까? 다음의 입력을 생각해 보자.

5 5
2
1 10 5
4 5 10

다른 요소가 동일하다면 회전율이 높은 트럭이 더 많은 상자를 배송할 수 있다. 위의 첫 번째 택배처럼 오랫동안 트럭을 점유하고 있으면 곤란하다.

 

즉 택배를 싣는 마을이 아니라 택배를 내리는 마을을 기준으로 생각해야 한다. 어디서 실었는지는 중요하지 않고, 일단 빨리 내릴 수 있는 택배를 먼저 배송해야 한다.

해결

주어진 입력을 받는 마을의 오름차순으로 정렬하고, 정렬된 순서대로 각 구간에서 배송할 수 있는 최대 수량만큼 배송하면 된다. 택배의 보내는 마을을 $from$, 받는 마을을 $to$, 보내는 수량을 $amount$라고 하면 이 택배는 $[from, to)$ 구간에서 $amount$만큼의 유량을 점유한다. 나는 배열을 선언하여 각 마을 사이의 현재 유량을 저장하였다.

---

코틀린 최고

의외로 2시간 동안 고민했던 문제. 문제를 자주 풀지 않아서 영..