배송 구간 분할
골드 III의견: 0
택배 회사 '리세네 배송'은 \(N\)개의 택배 상자를 순서를 유지하면서 정확히 \(K\)개의 배송 구역으로 나누어 배달한다. 각 배송 구역은 연속된 상자들로 이루어지며, 모든 상자는 정확히 하나의 구역에 속해야 한다.
\(i\)번 상자의 무게는 \(W_i\)이고, 각 구역의 무게 합은 그 구역에 속한 상자들의 무게 합이다.
모든 구역 중 무게 합의 최댓값을 최소화했을 때, 그 값을 구하여라.
- \(1 \le K \le N \le 200\,000\)
- \(1 \le W_i \le 10^9\)
첫째 줄에 상자의 수 \(N\)과 배송 구역의 수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 상자의 무게 \(W_1, W_2, \dots, W_N\)이 공백으로 구분되어 주어진다.
모든 구역의 무게 합 중 최댓값의 최솟값을 출력한다.
5 2
1 2 3 4 5
9
분할 \([1,2,3]\)과 \([4,5]\)의 최대 합은 \(9\)이다. 다른 분할들을 확인하면 \([1,2,3,4],[5]\) → \(10\), \([1],[2,3,4,5]\) → \(14\)이므로 최솟값은 \(9\).
5 2
7 2 5 10 8
18
최적 분할: \([7,2,5]\)와 \([10,8]\) → 최대 합 \(18\). \([7,2,5,10]\)과 \([8]\) → 최대 \(24\). 답은 \(18\).
riseoj 작성
출처 Original
평가 및 의견
배송 구간 분할
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
배송 구간 분할