본문 바로가기

알고리즘

출정 전야의 임무 배정

New Era · 1번Lv. 3이분 탐색

출정 전야의 임무 배정

문제 설명

라이캣의 출정 명령이 떨어졌습니다. 날이 밝으면 동료들은 비행정을 타고 라이언 타운으로 떠납니다. 그 전에 출정에 쓸 물자를 모두 비행정에 실어야 합니다.

파워 스톤을 받은 대리인 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개도 함께 채점해요.