Lv.3arraybinary-searchgreedyparametric-search
구간 합의 최댓값 최소화
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
양의 정수 배열 A를 순서를 바꾸지 않고 D개의 연속된 조각으로 나눕니다. 각 조각은 비어 있지 않습니다.
조각들의 합 중 최댓값을 최소화하세요. 그 최솟값을 반환합니다.
입출력 예
| A | D | result |
|---|---|---|
[1, 2, 3, 4, 5] | 2 | 9 |
[7, 2, 5, 10, 8] | 2 | 18 |
[1, 1, 1] | 3 | 1 |
입출력 예 설명
예 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
- 답은 64비트 정수 범위입니다.
Expected complexity
- Time
- O(N log(sum))
- Space
- O(1)
Examples
| A | D | Expected |
|---|---|---|
[1,2,3,4,5] | 2 | 9 |
[7,2,5,10,8] | 2 | 18 |
[1,1,1] | 3 | 1 |
Hint
Hint
답을 직접 구하는 공식은 없지만, 값 가 주어지면 "각 조각의 합이 이하가 되게 몇 조각으로 나뉘나?"는 쉽게 셀 수 있습니다. 앞에서부터 욕심껏 담다가 넘치면 새 조각을 시작하면 됩니다.
그리고 를 키우면 나누기가 더 쉬워집니다(단조성). 그러니 가능/불가능의 경계를 이분탐색으로 찾으면 됩니다.
while (lo < hi) {
mid = lo + (hi - lo) / 2; // 내림
if (Check(mid)) hi = mid; // 가능 → 더 작게
else lo = mid + 1;
}
return lo;
탐색 범위는 하한이 A의 최댓값(어떤 조각도 원소 하나보다 작을 수 없음), 상한이 전체 합(전부 한 조각)입니다.
복잡도 목표
가능한 모든 분할을 시도하는 풀이는 조각 수가 늘면 경우의 수가 폭발합니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |