아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 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이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.
출력
트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.
입력 예시
4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20
출력 예시
70
풀이
그리디 + 정렬 문제. 택배를 (도착지, 출발지-도착지 간 거리)를 기준으로 정렬한 후, 택배 리스트를 순회하면서 전체 거리 리스트를 차례대로 채워넣는다. 어떤 택배 원소가 start, end, box로 이루어졌다고 가정하자. 그렇다면, 거리 리스트의 (start, end-1) 구간의 최소값을 구하면 그 구간에서 실을 수 있는 택배의 최대 용량이 나온다. 이 최대 용량과 box중 더 작은 값을 실을 수 있으므로, 이 구간 (start, end-1)을 업데이트하고 배송 가능한 최대 박스 수에 이 값을 더해준다. 이를 모든 택배 리스트에 대해 수행하면 된다.
init : 초기화 함수, 문제 풀이에 필요한 인자들 및 택배 리스트 post_list를 입력받는다. post_list를 위의 정렬 조건에 맞추어 정렬한 후 반환한다.
greedy_search : 그리디 알고리즘을 수행하는 함수. 위에서 설명한 방법대로 배송 가능한 최대 박스 수 result를 구하여 이를 반환한다.
from heapq import *
import sys
input = sys.stdin.readline
def init() :
global N, C, M
N, C = map(int, input().split())
M = int(input())
post_list = [list(map(int, input().split())) for _ in range(M)]
post_list.sort(key = lambda x : (x[1], -x[0]))
return post_list
def greedy_search(post_list) :
global N, C
enable_list = [C]*(N+1)
result = 0
for start, end, box in post_list :
max_enable = min(enable_list[start:end+1])
enable_box = min(max_enable, box)
for i in range(start, end) :
enable_list[i] -= enable_box
result += enable_box
return result
def solve() :
post_list = init()
result = greedy_search(post_list)
print(result)
solve()
