택배

이틀동안 못풀었던 문제였는데, 다른 분의 힌트를 얻어 풀었다. 힌트를 이용해서 풀고 나니까, 이걸 왜 생각하지 못했지 라는 생각이 들었다.

처음에는 물건을 보내는 마을 번호가 가장 빠른 순으로 정렬해 풀었고, 이후에는 퇴사 문제를 풀듯이 DP를 사용하기도 했다. 물론 모두 틀렸었다…

물건들의 도착지가 빠른 순서대로 정렬을 한 이후에, 물건을 실을 수 있는 한 많이 실어주면 된다.

• sort함수를 활용해 두번째 값을 기준으로 오름차순 정렬을 해주었다.
• left라는 리스트를 만들어 각각의 마을에서 더 실을 수 있는 박스의 개수를 저장했다.
• 정렬된 박스 정보를 사용해 차례대로 실을 수 있는한 박스를 많이 실어준다.
• 박스를 보내는 마을에 대한 정보와 받는 마을에 대한 정보가 있다.

예제를 활용해서 이해해보자.(설명을 위해 다른 예시를 사용했다.)

4 40
3
1 2 10
1 3 20
2 4 30

1 2 10

• 1,2,10의 경우 1번째 마을부터 2번째 마을까지 10개의 박스를 옮겨야 한다.
• 2번째 마을은 박스를 받는 마을임으로 제외하고, 1번째 마을의 left값에서 10을 빼준다. 1번째 마을에는 이제 30개만 더 실을 수 있다.

1 3 20

• 1,3,20의 경우 1번째 마을부터 3번째 마을까지 20개의 박스를 옮겨야 한다.
• 3번째 마을은 박스를 받는 마을임으로 제외하고, 1번째 마을과 두번째 마을의 left값에서 20을 각각 빼준다. 1번째 마을은 10개, 2번째 마을은 20개의 박스를 더 실을 수 있다.

2 4 30

• 2,4,30의 경우 2번째 마을부터 4번째 마을까지 30개의 박스를 옮겨야 한다.
• 2번째 마을의 경우 20개의 박스를 더 실을 수 있고, 3번째 마을의 경우 40개의 박스를 더 실을 수 있다. 따라서 30개의 박스 중 20개만 옮길 수 있다.
• 4번째 마을을 제외하고 2번째, 3번째 마을의 left값에서 20씩을 빼준다. 2번째 마을은 0개의 박스를, 3번째 마을은 20개의 박스를 더 실을 수 있다.

이런식으로 박스들을 처리해 나가면 된다.

CODE

import sys
read = sys.stdin.readline

n, c = map(int, read().split())
m = int(read())
boxs = list(list(map(int, read().split())) for _ in range(m))
#물건의 도착지가 빠른 순으로 정렬
boxs.sort(key=lambda x: (x[1], x[0]))
#해당 마을에서 물건을 얼마나 더 실을 수 있는지 확인
left = list(c for _ in range(n+1))

answer = 0

for a, b, w in boxs:
    #a ~ b마을에서 물건을 더 실을 수 있는 값들의 최소값
    available = min(left[a:b])
    if available > 0:
        put = min(available, w)
        answer += put
        for i in range(a, b):
            left[i] -= put
print(answer)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]