2 minute read

8980번 : 택배

문제 링크

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

문제 설명

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 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. 빨리 내릴 수 있는 정보 순으로 정렬
  2. 이미 싣고있는 화물을 인식하고 화물을 실을때 최대 트럭 용량만큼 싣기
# 마을 수(N), 트럭 용량(C) 입력
N, C = map(int, input().split())

# 보내는 박스 정보 개수(M) 입력
M = int(input())

# 필요한 변수 선언
arr = []
truck = [0] * N
result = 0

# M번 보내는 마을 번호, 받는 마을 번호, 박스 개수 입력
for _ in range(M) :
    send, receive, box = map(int, input().split())
    arr.append((send, receive, box))

# 빨리 내릴 수 있는 정보순으로 정렬
arr.sort(key = lambda x : x[1])

# 배열 항목을 순회하면서
for temp in arr :     
    box = temp[2] 
         
    # (보내는 박스 + (보내는 마을 번호 ~ 받는 마을 번호까지 박스들 중 최대값))가 최대 트럭 용량만큼만 트럭에 싣기 
    box = box - max(box + max(truck[temp[0]:temp[1]]) - C, 0) 
    
    # 보내는 박스가 0보다 크면
    if box > 0 : 

        # truck 배열에 보내는 마을 번호 ~ 받는 마을 번호까지 박스값 더하기
        truck[temp[0]:temp[1]] = [i + box for i in truck[temp[0]:temp[1]]]
    
        # 실은 박스만큼 result에 더하기
        result += box
        
print(result)

Comments

You May Also Enjoy