아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽 으로 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개이다. 이는 배송할 수 있는 최대 박스 개수이다.
그리디 알고리즘을 적용하려면, '우선순위'를 생각해 보아야 한다. 여기서는 택배 트럭이 마을 사이를 이동할 때, 최대 수용량이 정해져 있다는 사실을 알 수 있다. 따라서 가급적 적은 거리를 이동하는 택배 화물이 우선순위를 갖는게 좋다. 그래야만 박스가 점유하는 시간이 적어지니까.
또한 생각해 볼 것은, 택배 트럭은 무조건 순서대로 이동한다는 점이다. 즉 어떤 도시 지점에서의 '적은 거리'를 고려한다면, 도착지가 가까운 순으로 우선순위를 부여하면 된다.
풀이 코드
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
M = int(input())
answer = 0
capacity_list = [C]*(N+1)
box_list = [list(map(int, input().split())) for _ in range(M)]
box_list.sort(key = lambda x : (x[1], x[2]))
for sender, receiver, box in box_list :
min_capacity = min(capacity_list[sender:receiver])
box_enabled = min(box, min_capacity)
if box_enabled > 0 :
answer += box_enabled
for i in range(sender, receiver):
capacity_list[i] -= box_enabled
print(answer)
