택배 트럭 분할
골드 III의견: 0
택배 회사는 컨베이어를 따라 일렬로 놓인 \(N\)개의 상자를 \(K\)대의 트럭에 나누어 싣는다. 상자 \(i\)의 무게는 \(a_i\)이다. 각 트럭은 연속한 구간의 상자들만 실을 수 있으며, 모든 상자는 정확히 한 트럭에 실린다. 즉 일렬의 상자들을 \(K\)개의 연속 구간으로 나누는 것이다(빈 구간은 없다고 하자).
어떤 트럭이 실은 상자 무게의 합을 그 트럭의 적재량이라 할 때, 가장 무거운 트럭의 적재량을 최소화하도록 나누고자 한다. 이때 가능한 최소의 최대 적재량을 구하여라.
\(1 \le N \le 200{,}000\), \(1 \le K \le N\), \(1 \le a_i \le 10^9\).
첫째 줄에 상자 수 \(N\)과 트럭 수 \(K\)가 주어진다 (\(1 \le K \le N\)). 둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 공백으로 주어진다.
가능한 최소의 최대 적재량을 한 줄에 출력한다.
5 2
3 1 4 1 5
8구간을 \([3,1,4]\) 와 \([1,5]\) 로 나누면 적재량이 8과 6이 되어 최대 8이다. 다른 어떤 2분할도 최대 적재량을 8보다 작게 만들 수 없으므로 정답은 8이다.
4 4
10 20 30 40
40\(K=N\) 이므로 각 트럭이 상자 하나씩 싣는다. 가장 무거운 상자가 40이므로 최대 적재량의 최솟값은 40이다.
riseoj 작성
출처 Original
평가 및 의견
택배 트럭 분할
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
택배 트럭 분할