[그리디] 백준 8980번: 택배 / 골드 3

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

8980번: 택배

n, c = map(int, input().split())
m = int(input())

lst = []
for i in range(m):
    lst.append(list(map(int, input().split())))
lst.sort(key=lambda x: x[1])

capacity = [0]*(n+1)
answer = 0
for start, end, load in lst:
    possible = True
    for i in range(start, end):
        if capacity[i] >= c:
            possible = False
            break

    if possible:
        left = c - max(capacity[start:end]) # left space
        add = load if left >= load else left
        for i in range(start, end):
            capacity[i] += add
        answer += add
print(answer)

풀이법을 생각하기 어려운 문제다.

그리디는 정말 생각하기 어려운것 같다... 풀어놓은 문제들을 여러번 복습할 필요가 있다.

이 문제의 핵심은 목적지가 빠른 순서대로 정렬하는 것이다.

짐을 빨리빨리 덜어낼수록 많은 배달을 할 수 있기 때문이다.

 

* 출발지로 정렬하면 다음 오류가 발생

4 10
3
1 4 10
2 3 9
3 4 9

일 때 마을1에서 10을 다 올려놓고 마을4까지 가기 때문에 10이 출력되지만

사실은 마을 1에서 1만 올리고 마을2에서 9, 마을3에서 9를 올리면 19개까지 배달이 가능해진다.

 

이러하여 목적지가 빠른 순으로 정렬한 뒤 순차적으로 탐색하는데

1. 현재 탐색하는 항목의 출발지~목적지에 해당하는 capacity를 확인하여 용량이 비었을 때만 2를 실행

2. 정해진 최대 용량이 있기 때문에 짐을 실을 때마다 capacity에 업데이트를 해주었다. 실을 수 있는만큼 실으면 된다.