[BOJ 8980, Python 3] 택배

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

8980번: 택배

 

조건 3을 다르게 해석해서 뻘짓하다가 겨우 풀었네요

 

풀이

문제를 읽어보면 트럭에 박스를 최대한 꽉 채워서 가는 것이 제일 좋을 거라고 바로 생각할 수 있을 겁니다.

그리고 박스를 최대한 꽉 채워서 가면서 배송할 수 있는 박스 수를 최대화하려면 늦게 도착하는 박스보다 일찍 도착하는 박스를 우선으로 배송하는 것이 좋겠네요. 그러면 정렬을 할 때 도착마을을 기준으로 오름차순 정렬을 하면 될 것 같습니다.

 

그러면 문제가 회의실 배정, 공주님의 정원과 비슷하게 풀 수 있습니다.

다만 다른 점은 최대로 들고갈 수 있는 박스 수를 추가로 구해야 한다는 것인데 마을의 수가 최대 1000개라서 마을크기 만큼의 배열을 만들어서 박스를 추가할 때마다 (시작마을) ~ (도착 마을 - 1)까지 추가된 박스 수를 더해주면 됩니다.

그래서 구간 내의 최댓값을 구하여 min(트럭의 용량 - 구간 내 최댓값, 추가할 박스 무게)를 하여 트럭에 넣을 수 있는 최대 박스 수를 구해주며 됩니다.

(도착 마을 - 1)인 이유는 도착 마을에서는 트럭에 도착마을에 배송할 물건을 빼고 새로운 박스들을 들여올 수 있기 때문입니다.

 

 

코드

바로 윗 문단 부분은 배열 구간에서 추가된 박스 수를 더해준다고 했지만, 저는 배열의 값을 트럭 용량으로 초기화시키고, 추가된 박스 수를 뺴주고 최솟값을 확인하였습니다.

 

n, c = map(int, input().split())
m = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(m)], key=lambda x: [x[1]])
box = [c] * (n + 1)
ans = 0
idx = 1
for i in range(m):
    val = min(arr[i][2], min(box[arr[i][0]:arr[i][1]]))
    for j in range(arr[i][0], arr[i][1]):
        box[j] -= val
    ans += val
print(ans)