출처
https://www.acmicpc.net/problem/8980
문제
트럭으로 마을에서 마을까지 배송을 하는데, 가장 많이 실어나를 수 있는 상자의 수를 구하는 문제이다.
접근방법
처음에는 출발점을 기준으로 정렬하여 트럭의 현재상황을 저장하는 배열에 순서대로 적재하는 방식을 통해 해결하려고 하였다. 하지만 1 -> 6 마을로 배달을 가는 경우 처럼 매우 비효율 적인 상황이 발생하였다.
그래서 기준을 '도착하는 마을'을 기준으로 오름차순 정렬 한 후, 마을과 마을 사이에 잔여 용량을 관리하는 배열 하나를 선언하여 빼주면서 진행하였다.
풀이
만약 예제가 아래의 경우처럼 주어졌다면,
6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40
도착점 기준으로 먼저 오름차순으로 정렬하면,
[[1, 2, 30], [3, 4, 40], [2, 5, 70], [5, 6, 60], [1, 6, 40]] 의 배열이 나오고, [60, 60, 60, 60, 60, 60]의 트럭 배열을 선언한다.
-
첫번째로 1과 2마을 사이의 트럭 용량과 내가 실어야하는것 중 최소를 구한다. 60과 30 -> 30을 마을 용량인 truck[1]에 빼준다.
[30, 60, 60, 60, 60, 60] -
두번째로 3~4 마을 사이의 최소와 실어야할 박스 수 중 최소를 마찬가지로 구하여 40을 빼준다.
[30, 60, 20, 60, 60, 60] -
다음으로 2번과 5 마을 사이의 최소는 20이고 상자는 70이므로 둘 중 작은 20을 사이마을에 빼준다.
[30, 40, 0, 40, 60, 60] -
위 과정을 반복 한 후 내가 빼준 수의 합이 결과이다.
코드
import sys
input = sys.stdin.readline
n, limit = map(int, input().split())
m = int(input())
arr = [list(map(int, input().split())) for i in range(m)]
trucks = [limit for i in range(n+1)]
arr.sort(key=lambda x: x[1])
result = 0
for i in arr:
min_box = limit
for j in range(i[0], i[1]):
min_box = min(min_box, trucks[j])
min_box = min(min_box, i[2])
for j in range(i[0], i[1]):
trucks[j] -= min_box
result += min_box
print(result)