원고 합치기 최소 비용
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
소설 한 권이 N개의 장으로 나뉘어 파일로 저장되어 있고, i번 장 파일의 크기는 sizes[i]입니다. 장의 순서는 바꿀 수 없습니다.
이웃한 두 파일을 하나로 합칠 수 있고, 이때 두 파일 크기의 합만큼 비용이 듭니다. 합쳐진 파일의 크기도 두 크기의 합입니다. 이 작업을 반복해 모든 장을 파일 하나로 만들 때 드는 비용 합의 최솟값을 반환하세요.
입출력 예
| sizes | result |
|---|---|
[40, 30, 30, 50] | 300 |
[1, 100, 1] | 203 |
[7] | 0 |
입출력 예 설명
예 1 — 40+30(70), 30+50(80)을 먼저 만들고 둘을 합치면(150) 입니다. 가운데 30+30부터 합치면 으로 더 비쌉니다.
예 2 — 어느 쪽 1을 먼저 100과 합쳐도 입니다. 양 끝의 1끼리는 이웃이 아니라서 먼저 합칠 수 없습니다.
예 3 — 이미 파일이 하나이므로 비용이 들지 않습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(sizes: int[]) → long
제한 사항
-
sizes.length -
sizes[i] - 답이 32비트 정수 범위를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N^2)
- 공간
- O(N^2)
입출력 예
| sizes | 기대 출력 |
|---|---|
[40,30,30,50] | 300 |
[1,100,1] | 203 |
[7] | 0 |
힌트
힌트
구간 DP
dp[i][j] = 구간 i..j의 파일들을 하나로 합치는 최소 비용이라 하면, 마지막 합치기는 어떤 경계 k에서 i..k와 k+1..j를 합치는 것이므로
입니다(는 구간 크기 합, 누적 합으로 ). 그대로 계산하면 이라 에서는 너무 느립니다.
크누스 최적화
opt[i][j]를 최솟값을 주는 k라 하면, 이 비용 함수는 다음 성질을 만족합니다.
그래서 k를 i..j-1 전체가 아니라 opt[i][j-1]..opt[i+1][j]에서만 찾으면 됩니다. 길이가 같은 구간들에 대해 탐색 범위의 합이 으로 망원(telescoping)되므로 전체 입니다.
이 성질은 가 사각 부등식(, )과 단조성을 만족하기 때문에 성립합니다. 구간 합은 사각 부등식을 등호로 만족합니다.
복잡도 목표
이 필요합니다. 모든 k를 시도하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 236 ms | 추정 |
| C++ (GCC, gnu++23) | 236 ms | 도출됨 |
| Python 3.13 | 4714 ms | 도출됨 |
| Java 25 | 1200 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1472 ms | 추정 |
| C# 14 (.NET 10) | 1472 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |