백준 8980 택배 파이썬

www.acmicpc.net/problem/8980

8980번: 택배

n,c = 4,10
m = 3
box = [[1,4,10],[2,3,10],[3,4,10]]

box.sort(key=lambda x: x[1])
print(box)
truck_capa = [c] * (m + 1)
ans = 0
for i in range(m):
  temp = c
  # 목적지까지 거쳐가는 마을 중 적재량이 가장 작은 적재량을 선택
  for j in range(box[i][0], box[i][1]):
    temp = min(temp, truck_capa[j])
  # 가장 작은 적재량이 실어야하는 박스보다 작다면 가능한 적재량. 적재량이 실어야하는 박스보다 크다면 박스. 즉 더 작은 값을 선택하는것이 최선.
  temp = min(temp, box[i][2])

  # 싯기로 선택한 수만큼 거쳐가는 마을에 적재량 감소 처리
  for j in range(box[i][0], box[i][1]):
    truck_capa[j]-=temp
  
  ans+=temp

print(ans)

# 핵심은 도착지 순으로 정렬 하는것과
# 마을별 가능 적재량을 저장하여 목적지까지 거쳐가는 마을 중 가장 적은 적재량만큼만 배달 하는것이다.

# 도착지가 가장 가까운 순으로 정렬
# 1. 가장 가까운 곳 의 도착지까지 거치는 마을 중 적재량이 가장 조금 남은곳을 찾아서 그만큼만 싯는다.
# 2. 제일 궁금했던 부분: 적재량이 가장 조금 남은곳을 찾아서 싯는 이유 - 거쳐가는 마을에서 적재량이 가장 조금 남은만큼만 실어야 도착지가 먼곳의 박스를 많이 실어서 거쳐가는 마을의 박스를 못싯는 일을 방지할 수 있다.
# 예를들어 1 -> 4 50박스 배달. 2 -> 3 10박스배달. 3-> 4 10박스배달 이고 최대 적재량이 50일때 1번 마을에서 50을 다 실어버리면 2번 3번 마을에선 여유 적재공간이 없기때문에 그냥 지나쳐야한다.
# 하지만 적재량이 가장 조금 남은 곳인 2번 마을의 40 을 찾아서 1번 마을에서 40박스만 싯는다면 2번마을에서 10박스를 싯고 3번마을에서 10박스를 내려주고 10박스를 싯고 4번마을에서 40+10박스를 내려줘서 총 60박스를 나를수있다.

# https://steadev.tistory.com/15 참고

이 문제의 핵심은

1. 출발마을순이 아니라 도착마을순으로 정렬하는것

2. 각 박스를 실었을때의 트럭의 남은 적재량을 저장하는것

3. 배달해야하는 (도착마을 오름차순으로 정렬된) 박스의 정보를 순회하면서, 도착지까지 거쳐가는 마을 가장 작은 적재량을 선택하여 박스를 실을 수 있는 적재량이면 박스를 다 싯고 아니면 적재량만큼만 싯는다.

4. 3번처럼 하는 이유는 도착마을순으로 정렬돼있기때문에 도착마을이 가까운 곳은 남은 적재량이 많다는게 보장돼 많은량을 실게되고

후에 나오는 도착마을이 먼 마을은 도착마을이 가까운 마을에서 이미 박스를 실었기 때문에 적게 실을수밖에 없다는것이다.

 

은근 어려웠던 문제.