[BOJ] 8980번 - 택배

 

[BOJ] 8980번 - 택배

 

https://www.acmicpc.net/problem/8980

8980번: 택배

 

알고리즘

---

트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

최대한 많은 박스들을 가져가야 함으로 그리디 알고리즘으로 생각하여 구현하였습니다.

처음에는 Truck을 Time에 따라 구현하였으나, 시간 복잡도가 부족하여 75점이 나왔기 때문에 후에

정렬된 박스들의 표를 보고 얼마나 보낼 수 있는지로 구현하여 O(NlogN) 으로 구현하였습니다.

 

1. 도착한 시간을 기반으로 정렬

2. 현재 Box로 갈 옮길 수 있는 양과 현재 범위 내에서 Box를 옮길 수 있는 양 중에 최소값을 사용하여 Box를 옮긴다.

3. Box는 시작 범위부터 마을 도착하기 전까지 Truck에서 소요된다.

 

코드

---

#BOJ 8980번
import sys
input = sys.stdin.readline

answer = 0
n , weight = map(int,input().split())
k = int(input())
box = [weight]*(n+1)

datas = sorted( [ list( map(int,input().split()) ) for _ in range(k) ] , key = lambda x :x[1] )

for data in datas :
    move = min( data[2] , min(box[data[0]:data[1]]) )
    for j in range( data[0] , data[1] ) :
        box[j] -= move
    answer += move

print(answer)