[python] 백준 8980 택배

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

8980번: 택배

 

문제 해결

• 택배를 옮길 수 있는 최대 개수를 구하는 문제
• 어떤 택배가 더 가중치 있고 하지 않으므로 그냥 많이 옮기면 된다.
• 그러면 가까운 거리를 많이 이용하면 좋다.
• 도착지점이 가까운 지점부터 나열하여 최대한 많이 담아서 가는 것이 좋다. ( ex: (0,3) 20개 (2,5) 40개 있다 했을 때 (0,3) 20개 + (2,5) 20개를 옮기는 것이랑 (2,5) 40개를 옮기는 것은 다르다. (0,3)20개 (2,5) 20개는 (3,5) 사이의 물건 20개를 추가로 옮길 수 있기 때문이다.

 

CODE

n, c = map(int, input().split()) # 마을 수, 용량
m = int(input())
boxes = [list(map(int, input().split())) for _ in range(m)]
boxes.sort(key=lambda x: x[1]) # 도착 지점이 가까운 것부터 나열
ans = 0 # 최대 운반 개수
upper_bound = [c]*(n+1) #지역마다 c개를 넘을 수 없음. 한계선

for i in range(m):
    temp = c # c개를 옮길 수 있다고 가정
    for j in range(boxes[i][0], boxes[i][1]): # 출발지점부터 도착지점까지
        temp = min(temp, upper_bound[j]) # 옮길 수 있는 것과 상한선중 작은 값
    temp = min(temp, boxes[i][2]) # 옮길 수 있는 상자 개수의 가능한 값과 실제 박스의 개수
    for k in range(boxes[i][0], boxes[i][1]):
        upper_bound[k] -= temp # 옮긴 것을 뺀다. 참고로 가까운 지역 도착 물건이기 때문에 옮기는 것이 확실
    ans += temp
print(ans)