백준[8980] 택배 (Python3)

쉬운 줄 알았는데 생각보다 많이 어려웠던 문제.
정렬 기준을 잘못 잡아서 삽질을 좀 했다.

지문 분석

트럭이 가장 많은 박스를 배송할 경우는, 박스들이 많이 있는 상황이다.
즉, 처음 출발할 때만 보면 된다.

그리고 박스를 최대한 많이 보내기 위해선, 박스들의 도착지가 현재 위치와 최대한 가까워야 한다. 따라서, 기존에 담긴 박스보다 새로 담을 박스가 더 배송지가 가깝다면 기존에 담긴 박스를 필요한 만큼 버린다.

지문에선 버린다는 표현은 없지만 나는 이런 식으로 이해하는 게 더 지문 분석이 쉬웠다.

시도한 방법 1

각 마을들에 대한 큐를 만들어 박스 배송 정보를 넣어준다.
트럭은 1번 마을부터 시작해 박스를 내리고 싣는다.
하지만 이 방법은 트럭에 있는 박스 배송 정보들이 출발지, 도착지 순으로 정렬된 상태여야 하는데 이 정렬된 형태를 유지하기 위한 조건 문과 코드가 생각보다 까다로웠다.
논리는 맞는 거 같았지만, 부분 점수를 맞아서 쉽게 생각할 필요가 있었다.

시도한 방법 2

지문 분석을 할 때, 기존에 담긴 박스보다 새로 담을 박스가 더 배송지가 가까운 경우 기존에 담긴 박스를 버려야 한다 했다.
그렇다면, 이 도착지가 가까운 박스를 미리 담아둔다는 식으로 접근했다.

박스 배송 정보를 도착지 순으로 오름차순 정렬한다.
그 후, 보내야 하는 박스의 개수를 미리 각 마을의 배열에 더해나간다.
단, 박스의 개수가 그 마을에서 실을 수 있는 트럭의 최대 수용량을 넘으면 안 된다.

이렇게 각 마을에 실을 수 있는 박스 개수를 미리 정했다면 그 값을 계속 합산한 것이 정답이 된다.

 

N, C = map(int, input().split())
M = int(input())
towns = [0 for _ in range(N + 1)]

boxes = []
for i in range(M):
    a, b, c = map(int, input().split())
    boxes.append((a, b, c))
boxes = sorted(boxes, key=lambda x: (x[1], x[0]))

ans = 0
for s, e, w in boxes:
    remain = 0
    # 현재 마을에 싣을 수 있는 박스 무게
    for i in range(s, e):
        remain = max(remain, towns[i])
    load = min(w, C - remain)
    ans += load
    for i in range(s, e):
        towns[i] += load
print(ans)