[백준 8980] 택배 (python)

8980번: 택배

---

 

그리디 알고리즘이다.

처음에는 시작점, 도착점을 기준으로 정렬을 했는데 도착점만을 기준으로 정렬을 해야했다.

1->5를 먼저하면 2->3, 3->4 와 같은 애들은 못할 수 있기 때문이다.

 

예시로 입력이 다음과 같을때 (도착점을 기준으로 정렬한 상태)

6 40
1 2 10
1 3 20
2 3 10
1 4 30
2 4 20
3 4 20

1. 마을들의 수용가능 박스수를 나타내는 box 배열을 생성한다.

 

1	2	3	4
40	40	40	40

 

2. 첫번째 요소가 [1, 2, 10] 이므로 1이상 2미만 마을의 최소값(40)과 실을 박스(10) 중 작은 값을 정한다. 그리고 그 박스는 1에서 실어서 2에서 내리므로 그 사이 마을에서 수용가능 박스수를 줄여준다.

 

1	2	3	4
30	40	40	40

 

3. 두번째 요소 [1, 3, 20]는 1이상 3미만 마을의 최소값(30)과 실을 박스(20) 중 작은 값을 정하고, 사이 마을 수용가능 박스수를 줄여준다.

 

1	2	3	4
10	20	40	40

 

4. 이런식으로 반복하여 답을 구한다.

 

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
M = int(input())
arr = []
for _ in range(M):
    arr.append(list(map(int, input().split())))
arr.sort(key=lambda x: x[1])

box = [C]*(N+1)
answer = 0
for s, e, b in arr:
    _min = C
    for i in range(s, e):
        _min = min(_min, box[i])
    _min = min(_min, b)
    for i in range(s, e):
        box[i] -= _min
    answer += _min

print(answer)