[백준 8980] 택배 - Python

문제 보기

 

[사용한 알고리즘]

그리디(Greedy), 정렬

 

[알고리즘]

1. 도착 순서가 빠른 순서로 박스를 정렬합니다.

2. 마을의 수와 길이가 동일한 배열을 선언합니다. (초기값은 트럭의 최대 용량입니다)

3. 현재 박스의 출발 위치에서 도착 위치로 배송할 수 있는 만큼 최대한 박스를 배송합니다.

 - 2번에서 선언한 배열에는 각 위치에 배송할 수 있는 최대 박스 크기가 저장되어 있습니다. 따라서 출발 위치에서 도착 위치 사이에 있는 배열의 값 중 가장 작은 값과 현재 배송할 박스의 수 중 작은 값을 최종적으로 배송할 수 있습니다.

 

[코드]

import sys

if __name__ == "__main__":
    n, c = map(int, sys.stdin.readline().split())
    m = int(sys.stdin.readline())
    box = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]


    box.sort(key=lambda x:x[1])  # 도착 시간이 빠른 순서로 정렬

    answer = 0  # 최대 박스 수
    remain = [c] * (n + 1)  # 각 위치에 남은 공간

    for i in range(m):
        temp = c  # c개를 옮길 수 있다고 가정
        for j in range(box[i][0], box[i][1]):
            temp = min(temp, remain[j])
        temp = min(temp, box[i][2])
        for j in range(box[i][0], box[i][1]):
            remain[j] -= temp
        answer += temp

    print(answer)