[백준] [파이썬] [그리디] 8980번: 택배

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

8980번: 택배 문제보기

 

시간 제한: 1 초
메모리 제한: 128 MB

문제

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

입력

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

예제 입력 1

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

예제 출력 1

70

예제 입력 2

6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40

예제 출력 2

150

---

어렵다...

이 문제를 보면 가장 먼저 다음과 같은 생각의 흐름을 갖게 된다. 

 

1. 가장 먼저 1번 마을에 도착하면 

1출발4도착 30박스는 10박스 밖에 못싣는다     -> 40

트럭 남은 용량:0

 

2. 2번 마을에 도착하면 

10개의 박스를 내리고 

10개의 박스를 싣을 수 있다                            -> 40+10=50 

트럭 남은 용량:0

 

3. 3번 마을에 도착하면 

20개의 박스를 내리고 10개의 박스를 내린다 

그리고 20개의 박스를 싣는다.                    -> 50+20=70

트럭 남은 용량:10

 

4. 4번 마을에 도착하면 

4번 마을에서 남은 박스 다 내리고 더 넣을 상자는 없으므로 

답은 70이 된다.

---

그러나

가장 중요한 핵심은 "도착지를 기준으로 빠른 도착지의 박스부터 싣는것이 최적"해이다.

각 마을에서 실을 수 있는 트럭용량을 배열로 저장하고, 빠른 도착지부터 출발지-도착지 사이의 택배용량을 줄여나가는 방법이다.  

 

1. 출발지, 도착지, 박스개수를 저장하고 도착지 오름차순으로 정렬한다.

2. 각 마을에서의 트럭 용량을 기록할 배열을 만든다.

3. 출발지-도착지 사이 마을의 트럭 용량에서 박스 개수만큼을 뺀다. 

4. 지금까지 뺐던 박스 총 개수를 반환한다.

 

오름차순이 되면 [[1, 2, 10], [1, 3, 20], [2, 3, 10], [3, 4, 20], [1, 4, 30], [2, 4, 20]]

 

과정

 

1출발2도착 10박스를 싣는다 -> 트럭의 용량은 1마을에서 40-10= 30이 된다 

1출발3도착 20박스를 1,2마을에 싣는다 -> 트럭용량은 1마을에서 30-20=10, 2마을에서 40-20=20이 된다. 

2출발3도착 10박스를 2마을에 싣는다 -> 트럭용량은 2마을에서 20-10=10

3출발4도착 20박스를 3마을에 싣는다 -> 트럭용량은 3마을에서 40-20=20

 

 

1출발4도착 30박스는 1,2,3마을에 30개의 박스를 다 못 싣는다 . 1번 마을에 최대 10개의 박스 밖에 못싣기 때문에

res += 10을 해준다.

 

 

업데이트 없이 끝

1출발4도착 10개의 박스를 1번,2번,3번마을에 -10씩 해주면 위와 같은 표가 되고 

2출발4도착 30박스는 이미 2번 마을에 싣을 여유가 없으므로 업데이트 없이 끝난다. 

 

---

정답 코드

import sys
from collections import deque

input=sys.stdin.readline


if __name__=="__main__":
    N,C=map(int, input().split())       # 마을개수, 트럭용량
    M=int(input())                      # 박스의 정보
    infos=[]
    for _ in range(M):
        start,end,nums=map(int,input().split())
        infos.append([start,end,nums])

    # 1단계
    infos.sort(key=lambda x: x[1])  # 가장 빨리 도착하는 순서대로 도착지 오름차순
    Truck_C=[C]*N               # 각 마을에서의 트럭 용량을 기록할 배열 초기화
    res=0
    for s,r,box in infos:
        min_c=C
        # 2단계 s에서 r로 이동하면서 
        for i in range(s,r):    # s마을에서 r마을까지 가면서 내릴 수 있는 박스 개수 업데이트하기위해
            if min_c>min(Truck_C[i],box):
                min_c=min(Truck_C[i],box)   # 새로운 용량 업데이트
        
        # 3단계 출발지-도착지 사이 마을의 트럭 용량(Trucj_C[i])에서 업데이트 된 박스개수(min_c) 만큼 뺀다   
        for i in range(s,r):    # 출발지-도착지 사이 마을의 트럭 용량에서 박스 개수 만큼 뺀다
            Truck_C[i]-=min_c               # i위치에서 새로운 용량 업데이트
        res+=min_c

    print(res)

---

너무 어려워... 이걸 어떻게 풀어...