[ 백준 / 파이썬 ] 골드 1 - 8980. 택배

난이도

문제

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

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

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

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

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	30
2	3	10
2	4	20
3	4	20

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	10

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

보내는 마을	받는 마을	박스 개수
2	3	10

(3) 3번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

보내는 마을	받는 마을	박스 개수
3	4	20

(4) 4번 마을에 도착하면

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

서브태스크

번호	배점	제한
1	15	보내는 마을번호는 모두 1, N ≤ 20
2	17	받는 마을번호는 N-1 또는 N, 3 ≤ N ≤ 20
3	20	N ≤ 5, M ≤ 5, C ≤ 10
4	23	N ≤ 100, M ≤ 1,000, C ≤ 2,000
5	25	추가적인 제약조건은 없다.

예제

입력	출력
4 40 6 3 4 20 1 2 10 1 3 20 1 4 30 2 3 10 2 4 20	70

입력	출력
6 60 5 1 2 30 2 5 70 5 6 60 3 4 40 1 6 40	150

풀이

이 문제만 1시간 30분 넘게 푼 것 같다.
그리디 알고리즘으로 분류되어 있어서 그리디 하게 풀어보려고 하는데, 도저히 방법을 찾을 수 가 없었다.

처음에는 빠른 것부터 전부 담았는데, 역시나 안되고..
그래서 거리별 가격으로 max_heap 을 만들었는데, 구현이 안된다...

정답은 도착하는 마을 순서로 정렬한 뒤, 모든 택배를 배송하는 것이다.

이 때, 배송할 물건마다 트럭의 용량을 잘 확인해야한다.

1. 택배 용량이 80일 때, 택배는 마을에 도착하면 모두 내린다.

2. 1번 마을에서 4번 마을로 30개의 택배를 보내면, 1번 마을부터 3번 마을 까지 30개의 택배 물량을 싣고 있는 것이다.

3. 그 다음 2번 마을에서 5번 마을로 60개의 택배를 보내면, 2번 마을 부터 3번 마을까지 이미 30개를 싣고 있기 때문에 최대 50개만 실을 수 있다.
   그러면 2번 마을부터 3번 마을은 80개의 택배가 실려있고, 4번 마을은 50개가 실려있다.

4. 그 다음 3번 마을에서 8번 마을로 40개의 택배를 보내면, 3번 마을에 이미 80개가 실려있기 때문에 아무것도 보낼 수 없다.

위 처럼 누적되는 택배 수를 잘 관리해야한다.

코드

from sys import stdin
from collections import deque


input = stdin.readline


def solution():

    N, C = map(int, input().split())
    M = int(input())

    boxes = list(tuple(map(int, input().split())) for _ in range(M))
    boxes.sort(key=lambda x: x[1])
    boxes = deque(boxes)

    capacities = [0] * (N + 1)

    towns = [0] * (N + 1)

    while boxes:
        start, finish, cost = boxes.popleft()

        cost = min(C - max(capacities[start: finish]), cost)

        for i in range(start, finish):
            capacities[i] += cost
            if capacities[i] > C:
                capacities[i] = C

        towns[finish] += cost


    return sum(towns)


print(solution())