우주 택배
실버 III의견: 0
미래 도시의 물류 회사 '스타십 로지스틱스'는 소포 \(N\)개를 드론 \(M\)대로 배달해야 한다. 소포는 번호 순서대로 정렬되어 있고, 각 드론은 연속된 구간의 소포만 담을 수 있다. 드론 \(M\)대가 번호 \(1\)번부터 \(N\)번까지의 소포를 남김없이 나누어 맡는다 (비어 있는 드론은 없어도 된다).
드론 한 대의 최대 적재 용량은 \(C\)이며, 한 드론이 맡은 소포 무게의 합이 \(C\)를 넘으면 안 된다. 배달을 완료하기 위한 최소 용량 \(C\)를 구하여라.
- \(1 \le M \le N \le 200\,000\)
- 각 소포의 무게는 \(1\) 이상 \(10^9\) 이하의 정수이다.
- 소포 무게의 총합은 \(10^{14}\) 이하이다.
첫째 줄에 소포의 수 \(N\)과 드론의 수 \(M\)이 공백으로 구분되어 주어진다.
둘째 줄에 소포의 무게 \(N\)개가 번호 순서대로 공백으로 구분되어 주어진다.
배달을 완료하기 위한 최소 적재 용량 \(C\)를 출력한다.
5 2
3 2 4 1 5
9
드론 \(2\)대가 연속 구간을 맡는다. 용량 \(9\)이면 \([3,2,4]\)와 \([1,5]\)로 나눌 수 있다. 용량 \(8\)이면 \([3,2,4]\)는 합이 \(9 > 8\)이 되어 불가능하다. 따라서 최소 용량은 \(9\)이다.
5 3
1 2 3 4 5
6
드론 \(3\)대로 \([1,2,3]\), \([4]\), \([5]\) 로 나누면 최대 합 \(6\). 용량 \(5\)이면 \([1,2]\), \([3]\), \([4,5]\)는 \([4,5]=9 > 5\)가 되어 불가능. 답은 \(6\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
우주 택배
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
우주 택배