[백준 8980번] 택배 (python)

문제

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

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

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

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

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	30
2	3	10
2	4	20
3	4	20

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	10

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

보내는 마을	받는 마을	박스 개수
2	3	10

(3) 3번 마을에 도착하면 

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

보내는 마을	받는 마을	박스 개수
3	4	20

(4) 4번 마을에 도착하면 

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

 

기록

(greedy 8일차) 한참 자신감 오르고 있었는데 이 문제 풀면서 다시 겸손해졌다. 처음에 마을 차례대로 돌면서 택배를 일단 모두 실을 수 있을만큼 싣고, 어떤 목적지의 택배던지 상관안하고 도착지마다 가지고있는 택배를 무조건 최대로 내리도록 구현했다. 왜 이 방법이 맞는지 이유도 설명 못하면서 무작정 확신했었다. 무식하면 용감하다더니.....!!!!!!! 내 얘긴가보다ㅠ 앞으로는 이 풀이가 왜, 어떻게 이 문제에서 최선의 선택이 될 수 있는지 설명하는 연습을 해볼까 싶다. 아래는 나에게 적용되었던 반례이다.

5 30
5
1 2 30
1 3 20
2 5 30
3 4 10
4 5 10
# 틀린답:80
# 답:70

여튼 전혀 모르겠어서 구글링해서 다시 풀었다. 일단 가장 중요한 점은 빠른 도착지의 박스부터 싣는것이 최적해라는 것이다! 풀이는 아주 직관적이었다. 각 마을에서 실을 수 있는 트럭용량을 배열로 저장하고, 빠른 도착지부터 출발지-도착지 사이의 택배용량을 줄여나가는 방법이다.  

 

참고로 시간초과가 나온 이유는 이 문제가 서브태스크 단위로 채점하다보니 시간초과여도 멈추고 점수가 뜰 것 같다는 생각에 무한 반복문 돌려봤다. 그랬더니 점수가 아니라 시간초과라고 잘 뜨는 것을 확인할 수 있었다:)

 

 

코드

from sys import stdin

N, C =  map(int, stdin.readline().split())
M = int(stdin.readline())
infos = []
for _ in range(M):
    s, r, box = map(int, stdin.readline().split())
    infos.append((s, r, box))
infos.sort(key=lambda x :  x[1])

capa = [C]*N
total = 0
for s, r, box in infos:
    _min = C
    for i in range(s, r):
        if _min > min(capa[i], box) :
            _min = min(capa[i], box)
    for i in range(s, r):
        capa[i] -= _min
    total += _min
print(total)

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

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

3. 출발지-도착지 사이 마을의 트럭 용량에서 박스 개수만큼을 뺀다. ( 박스개수가 트럭용량보다 작을경우 트럭용량을 뺀다 )

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