문제 설명
길이가 서로 다른 N개의 강의 영상을 cnt개의 DVD에 저장하고자 합니다.
- 각 DVD에는 강의 영상을 반드시 순서대로 연속되게 담아야 합니다.
- 하나의 강의를 나누어 여러 DVD에 저장하는 것은 허용되지 않습니다.
목표는 모든 강의를 cnt개의 DVD에 분배할 때 DVD 하나가 담아야 하는 최대 재생 시간을 최소화하는 것입니다.
강의 순서대로 영상 길이 정보가 담긴 배열 lectures와 DVD의 개수 cnt가 주어졌을 때, 위의 조건을 만족하는 최대 재생 시간의 최솟값을 반환하는 solution 함수를 작성하시오.
예를 들어, lectures가 [1, 2, 3, 4, 5, 6, 7, 8, 9]이고 cnt가 3이라면, 총 9개의 강의를 3개의 DVD로 나누어 저장해야 합니다.
만약 [1,2,3], [4,5,6], [7,8,9]과 같이 묶어 DVD에 저장하면 각 DVD의 총 재생 시간은 6, 15, 24이고 최댓값은 24입니다.
반면 [1,2,3,4,5], [6,7], [8,9]처럼 나누면 각 DVD의 총 재생 시간은 15, 13, 17이고 최댓값은 17입니다.
모든 방법을 고려했을 때 DVD의 최대 재생 시간은 17보다 작아질 수 없으므로 이 경우 17을 반환합니다.
제한 사항
lectures의 길이는 1 이상 100,000 이하입니다.lectures의 각 원소는 1 이상 1,000 이하의 자연수입니다.cnt는 1 이상 100,000 이하의 자연수입니다.
예시 테스트케이스 설명
| 테스트케이스 번호 | lectures | cnt | return |
|---|---|---|---|
| 1 | [1,2,3,4,5,6,7,8,9] | 3 | 17 |
| 2 | [6,2,3,5,5] | 2 | 11 |
| 3 | [4,8,1,7,2,6,5] | 7 | 8 |
1번 테스트케이스 설명
[1,2,3,4,5] | [6,7] | [8,9]처럼 세 구간으로 나누면, 각 DVD의 재생 시간은 15, 13, 17이 되어 최댓값은 17입니다. 해당 경우가 최대 재생 시간이 최소가 되는 경우입니다.
2번 테스트케이스 설명
[6,2,3] | [5,5]처럼 두 구간으로 나누면, 각 DVD의 재생 시간은 11, 10이 되어 최댓값은 11입니다. 해당 경우가 최대 재생 시간이 최소가 되는 경우입니다.
3번 테스트케이스 설명
[4] | [8] | [1] | [7] | [2] | [6] | [5]처럼 일곱 구간으로 나누면, 각 DVD의 재생 시간은 4, 8, 1, 7, 2, 6, 5가 되어 최댓값은 8입니다. 해당 경우가 최대 재생 시간이 최소가 되는 경우입니다.