Funcia
Lv.3arraybinary-searchgreedyparametric-search

구간 합의 최댓값 최소화

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
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입니다.

효율성

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

Function signature

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

Constraints

  • 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비트 정수 범위입니다.

Expected complexity

Time
O(N log(sum))
Space
O(1)

Examples

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

Hint

Hint

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

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

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

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

복잡도 목표

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

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.