[백준/Python]8980: 택배

문제

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

백준 문제집 - 0x11강 - 그리디

 

알고리즘: 그리디, 정렬

---

풀이

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

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.
조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
조건 3: 박스들 중 일부만 배송할 수도 있다.

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

정렬 기준이 키포인트인 문제다.

마을 순회가 1 ~ N 순으로 이어져서 보내는 마을 기준으로 정렬했지만 틀린 방법이었다 ^^;

적재할 수 있는 택배의 양이 정해져있으므로, 트럭 공간을 최대한 빨리 비울수록 가능한 적재량이 늘어난다!

따라서 배송 리스트를 "받는 마을" 순으로 오름차순 정렬해야한다.

 

또한 여유공간에 따라 싣을 수 있는 택배량이 달라지므로, 각 마을에서의 트럭 용량을 기록한다.

boxes = [tuple(map(int, input().split())) for _ in range(M)]
boxes.sort(key=lambda x: x[1])  # 받는 마을 번호 기준으로 정렬
capacity = [C] * (N + 1)  # 각 마을의 트럭 최대 용량

 

위에서 정렬한 배송 리스트를 순회하며 트럭 용량과 배송한 박스 수를 업데이트한다.

각 리스트는 (보내는 마을, 받는 마을, 택배상자 수)로 구성되어있다. 이를 (s, e, box)로 순회한다고 가정해보자.

 

트럭에 여유 공간에 따라 싣을 수 있는 택배의 수가 달라지므로, 여유공간부터 체크해야한다.

먼저 트럭 용량 리스트의 s부터 e-1번째까지의 값 중 가장 작은값을 찾는다.

어차피 택배는 e 마을에 도착하면 내릴것이므로 e-1번째 마을까지의 여유공간만 체크하면 된다.

또한 e-1번째 마을까지 쭉 싣고있어야하므로 최소값을 구해야한다.

그리고 본래 실으려 했던 box와 위에서 구한 최소값을 비교하여 더 작은값만큼을 트럭에 싣는다.

 

실었으면 여유 공간을 수정해줘야한다.

트럭 공간 리스트를 s부터 e-1번째까지 순회하며 실제 실은 택배 수 만큼 빼준다.

 

다음 순회로 넘어가기 전 배송한 박스 수에 실은 택배 수를 더한다.

 

전체 코드

# ⭐ 받는 마을 기준으로 정렬해야함. 트럭 공간을 더 빨리 비울수록 가능한 적재량이 늘어나기 때문!
# 메모리: 34456KB / 시간: 960ms
from sys import stdin


input = stdin.readline

N, C = map(int, input().split())
M = int(input())
boxes = [tuple(map(int, input().split())) for _ in range(M)]
boxes.sort(key=lambda x: x[1])  # 받는 마을 번호 기준으로 정렬

capacity = [C] * (N + 1)  # 각 마을의 트럭 최대 용량
total_box = 0

for s, e, box in boxes:
    available = min(capacity[s:e])  # s ~ e 마을 사이에서 가능한 최대 공간
    max_box = min(box, available)  # 실제로 배송 가능한 상자 수

    for i in range(s, e):
        capacity[i] -= max_box  # 가능한 상자 수만큼 s ~ e 공간 업데이트
    
    total_box += max_box

print(total_box)

참고로 주는 마을의 순서는 고려하지 않아도 된다. 어차피 트럭은 항상 왼쪽에서 오른쪽으로 진행되므로, 어느 마을을 먼저 따지던 최종 적재량은 같게된다.

 

아리까리 하다면 예시와 함께 보자.

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

# 답: 150

예제 2번이다.

 

받는 마을 기준으로 오름차순 정렬하면 아래와 같다.

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

 

첫번째부터 마지막까지 순회 과정이다.

 

# 첫번째 순회
capacity = [60, 60, 60, 60, 60, 60, 60]
total_box = 0

s, e, box = 1, 2, 30
min(capacity[s:e]) = 60
min(60, box) = 30


# 두번째 순회
capaticy = [60, 30, 60, 60, 60, 60, 60]
total_box = 30

s, e, box = 3, 4, 40
min(capacity[s:e]) = 60
min(60, box) = 40


# 세번째 순회
capaticy = [60, 30, 60, 20, 60, 60, 60]
total_box = 70

s, e, box = 2, 5, 70
min(capacity[s:e]) = 20
min(20, box) = 20


# 네번째 순회
capacity = [60, 30, 40, 0, 40, 60, 60]
total_box = 90

s, e, box = 5, 6, 60
min(capaticy[s:e]) = 60
min(60, box) = 60


# 다섯번째 순회
capacity = [60, 30, 40, 0, 40, 0, 60]
total_box = 150

s, e, box = 1, 6, 40
min(capatity[s:e]) = 0
min(0, box) = 0


# 순회 후 결과
capacity = [60, 30, 40, 0, 40, 0, 60]
total_box = 150