[Python] Baekjoon - 8980. 택배

백준 8980번 택배는 직선 위의 마을을 순서대로 운행하는 트럭이 상자를 총 몇 개 배달하는지 맞히는 문제다. 현재 마을에서 상자를 최대한 효율적으로 담아가야 하기 때문에 그리디 알고리즘을 사용하여 해결할 수 있다. 난이도는 골드 3이다.

 

백준 8980번 택배 문제 정보

알고리즘 분류

- 그리디 알고리즘 및 정렬

난이도

- 골드 3

 

택배 문제 요약

왼쪽 첫 번째 마을부터 맨 오른쪽 마지막 마을까지 순서대로 운행하는 트럭이 있다. 각 마을에서 보낼 상자의 개수(출발 마을, 도착 마을, 개수)와 트럭의 용량이 주어질 때, 마지막 마을까지 도착한 후 배달한 총 상자의 개수를 구하는 문제다.

 

문제 풀이 과정

• 현재 마을에서 상자를 최대한 효율적으로 담아가는 그리디 알고리즘을 사용한다.
• 더 가까운 도착지 우선으로 상자를 담는다.
• 현재 트럭에 담겨있는 상자를 버릴 수도 있다.

자세한 풀이

• delivery_list[s]: s 마을에서 출발하고 d 마을에 도착하는 상자의 개수 n에 대한 정보를 (d,n) 쌍의 리스트로 저장
• box_on_truck[d]: 현재 트럭이 싣고 있는 상자 중 d 마을이 목적지인 상자의 개수를 저장
• 매번 마을(here)에 도착할 때마다 box_on_truck[here]을 내려놓고, 트럭을 다시 채운다.

코드

import sys


def get_max_delivery():
    global N, C, delivery_list, box_on_truck

    delivered = 0
    for here in range(1, N+1):
        # 현재 마을에 내릴 박스 내리기
        delivered += box_on_truck[here]

        rest = C
        # 트럭에 자리 있으면 배달지 가까운 순으로 싣기
        for i in range(here+1, N+1):
            if rest > 0:
                # 싣고 있던거 그대로 놔두기
                if box_on_truck[i] > rest:
                    box_on_truck[i] = rest
                rest -= (box_on_truck[i])

                # 새로 싣기
                if delivery_list[here][i] > rest:
                    box_on_truck[i] += rest
                    rest = 0
                else:
                    box_on_truck[i] += delivery_list[here][i]
                    rest -= (delivery_list[here][i])
            else:
                box_on_truck[i] = 0

    return delivered


if __name__ == '__main__':
    N, C = map(int, input().split())
    M = int(input())
    delivery_list = [[0 for _ in range(N+1)] for _ in range(N+1)]
    box_on_truck = [0 for _ in range(N+1)]

    for _ in range(M):
        f, t, b = map(int, sys.stdin.readline().split())
        delivery_list[f][t] = b

    print(get_max_delivery())