8980. 택배 (Python)

8980번: 택배

 

풀이

 먼저 입력 받은 박스 정보를 받는 마을이 빠른 순으로 정렬해주고 받는 마을이 빠른 쪽에 최대한 많은 박스를 보낼 수 있도록 트럭에 실어주면 된다. boxInTruck이라는 배열을 사용하였는데 boxInTruck[i]의 뜻은 i번째 마을에서 현재 트럭에 실린 박스의 개수를 의미한다. 보내는 마을부터 받는 마을의 바로 이전 마을까지 트럭에 가장 많은 박스가 담겨 있는 경우와 비교했을 때 트럭에 박스를 더 실을 수 있을 경우 실을 수 있는 만큼의 박스를 더 담아주면 되고 그만큼을 배송할 수 있는 박스의 개수에 더해나간다.

 

 문제의 예제 2번을 살펴보면 다음과 같다. 

 위와 같은 상황에서 보내는 마을이 2이고 받는 마을이 5이며 박스 개수는 70을 처리하는 과정은 다음과 같다.

• 2번 마을에서 4번 마을까지의 트럭에 실린 박스의 최대 개수는 40개이다.
• 따라서 현재 2번 -> 5번의 70개 중 남은 트럭 용량인 20개 만큼을 추가로 실을 수 있음을 알 수 있다.
• 2번에서 4번 마을까지 +20을 해준다.
• 20을 결과 변수에 추가한다.

 

 위와 같은 과정을 반복해 나가면 된다.

 

코드

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N, C = map(int, input().split())  # N: 마을의 수, C: 트럭의 용량
    M = int(input())  # M: 보내는 박스 정보의 개수
    boxes = []
    
    # boxInTruck[i]: 트럭이 i번째 마을에 있을 때 실려 있는 박스의 최대 개수
    boxInTruck = [0 for _ in range(N+1)]

    for _ in range(M):
        s, e, box = map(int, input().split())
        boxes.append((s, e, box))

    boxes.sort(key=lambda x: (x[1], x[0]))  # 받는 마을이 빠른 순으로 정렬
    res = 0  # 배송할 수 있는 최대 박스 개수
    for (s, e, box) in boxes:  # s: 보내는 마을, e: 받는 마을, box: 보내는 박스 개수
        maxBox = max(boxInTruck[s:e])  # s부터 e-1번 마을까지의 트럭에 실린 박스 개수 중 최대 개수
        restTruck = C - maxBox  # 트럭에 실을 수 있는 박스의 개수

        if restTruck == 0:  # 더 이상 트럭에 실을 수 없는 상태라면 continue
            continue

        # 트럭에 실을 수 있는 박스 개수와 보내는 박스 개수 중 작은 값이 트럭에 추가로 실을 박스의 개수이다
        moveBoxCount = min(restTruck, box)
        # s번 마을부터 e-1번 까지 추가로 실을 박스의 개수를 boxInTruck에 더해준다.
        for i in range(s, e):
            boxInTruck[i] += moveBoxCount
        res += moveBoxCount  # 배송할 수 있는 박스 개수에 추가로 실을 박스를 추가해준다.

    print(res)