문제 설명

라이캣의 출정 명령이 떨어졌습니다. 날이 밝으면 동료들은 비행정을 타고 라이언 타운으로 떠납니다. 그 전에 출정에 쓸 물자를 모두 비행정에 실어야 합니다.
파워 스톤을 받은 대리인 No.1이 로봇 대리인들을 선착장으로 불러 모았습니다. 선착장을 따라 창고가 한 줄로 늘어서 있고, 창고마다 짐을 모두 싣는 데 걸리는 시간(분)이 정해져 있습니다.
"짐을 나르다 서로 부딪히면 안 된다냥. 대리인 한 명은 서로 붙어 있는 창고들만 맡는다냥!"
대리인들은 모두 동시에 일을 시작하고, 각자 맡은 창고의 짐을 차례로 싣습니다. 대리인 한 명이 일하는 시간은 맡은 창고들의 시간을 모두 더한 값입니다. 가장 늦게 끝나는 대리인까지 일을 마쳐야 비행정이 뜰 수 있습니다.
창고별 시간 목록 times(선착장에 늘어선 순서)와 대리인 수 n이 주어집니다. 창고들을 순서를 바꾸지 않고 n개 이하의 이어진 묶음으로 나눠 대리인들에게 맡길 때, 가장 늦게 끝나는 대리인의 일하는 시간을 가장 짧게 하면 몇 분인지 구하세요.
- 모든 창고는 정확히 한 대리인이 맡습니다. 창고 하나를 여러 대리인이 나눠 맡을 수는 없습니다.
- 창고를 하나도 맡지 않는 대리인이 있어도 됩니다.
제한 사항
- 입력은
[times, n]형태입니다. - 1 ≤
times의 길이 ≤ 10,000 - 1 ≤
times의 원소 ≤ 10,000 (정수) - 1 ≤
n≤times의 길이
입출력 예
| 입력 | 출력 |
|---|---|
| [[7, 2, 5, 10, 8], 2] | 18 |
| [[1, 2, 3, 4, 5, 6, 7, 8, 9], 3] | 17 |
| [[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8], 10] | 9 |
입출력 설명
첫 번째 예
대리인 2명에게 [7, 2, 5]와 [10, 8]로 나눠 맡기면 일하는 시간은 14분과 18분입니다. 가장 늦게 끝나는 대리인은 18분 걸립니다. [7, 2, 5, 10]과 [8]로 나누면 24분, [7, 2]와 [5, 10, 8]로 나누면 23분이 걸리므로 18분보다 짧게 끝낼 수는 없습니다.
두 번째 예
[1, 2, 3, 4, 5], [6, 7], [8, 9]로 나누면 15분, 13분, 17분이므로 17분 만에 모두 끝납니다.
세 번째 예
대리인이 10명이어도 9분이 걸리는 창고는 혼자 맡아도 9분이 걸립니다. 나머지 창고들을 9분이 넘지 않게 묶어 나머지 9명에게 맡길 수 있으므로 답은 9입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [[7, 2, 5, 10, 8], 2] | 18 |
| 2 | [[1, 2, 3, 4, 5, 6, 7, 8, 9], 3] | 17 |
| 3 | [[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8], 10] | 9 |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.