Funcia
Lv.3arraybinary-searchgreedyparametric-search

구간 합의 최댓값 최소화

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

양의 정수 배열 A를 순서를 바꾸지 않고 D개의 연속된 조각으로 나눕니다. 각 조각은 비어 있지 않습니다.

조각들의 합 중 최댓값을 최소화하세요. 그 최솟값을 반환합니다.

입출력 예

ADresult
[1, 2, 3, 4, 5]29
[7, 2, 5, 10, 8]218
[1, 1, 1]31

입출력 예 설명

예 1 — [1,2,3]과 [4,5]로 나누면 합이 6과 9라 최댓값이 9입니다. 이보다 나은 분할은 없습니다.

예 2 — [7,2,5]와 [10,8]로 나누면 14와 18이라 18입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(A: int[], D: int) → long

제한 사항

  • 1≤N≤200,0001 \le N \le 200{,}000
  • 1≤D≤N1 \le D \le N
  • 1≤A[i]≤1091 \le A[i] \le 10^9
  • 답은 64비트 정수 범위입니다.

기대 복잡도

시간
O(N log(sum))
공간
O(1)

입출력 예

AD기대 출력
[1,2,3,4,5]29
[7,2,5,10,8]218
[1,1,1]31

힌트

힌트

답을 직접 구하는 공식은 없지만, 값 XX가 주어지면 "각 조각의 합이 XX 이하가 되게 몇 조각으로 나뉘나?"는 쉽게 셀 수 있습니다. 앞에서부터 욕심껏 담다가 넘치면 새 조각을 시작하면 됩니다.

그리고 XX를 키우면 나누기가 더 쉬워집니다(단조성). 그러니 가능/불가능의 경계를 이분탐색으로 찾으면 됩니다.

while (lo < hi) {
    mid = lo + (hi - lo) / 2;      // 내림
    if (Check(mid)) hi = mid;      // 가능 → 더 작게
    else lo = mid + 1;
}
return lo;

탐색 범위는 하한이 A의 최댓값(어떤 조각도 원소 하나보다 작을 수 없음), 상한이 전체 합(전부 한 조각)입니다.

복잡도 목표

가능한 모든 분할을 시도하는 풀이는 조각 수가 늘면 경우의 수가 폭발합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251400 ms추정
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1000 ms도출됨

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.