Funcia
Lv.4dpinterval-dpknuth-optimization

원고 합치기 최소 비용

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

소설 한 권이 N개의 장으로 나뉘어 파일로 저장되어 있고, i번 장 파일의 크기는 sizes[i]입니다. 장의 순서는 바꿀 수 없습니다.

이웃한 두 파일을 하나로 합칠 수 있고, 이때 두 파일 크기의 합만큼 비용이 듭니다. 합쳐진 파일의 크기도 두 크기의 합입니다. 이 작업을 반복해 모든 장을 파일 하나로 만들 때 드는 비용 합의 최솟값을 반환하세요.

입출력 예

sizesresult
[40, 30, 30, 50]300
[1, 100, 1]203
[7]0

입출력 예 설명

예 1 — 40+30(70), 30+50(80)을 먼저 만들고 둘을 합치면(150) 70+80+150=30070 + 80 + 150 = 300입니다. 가운데 30+30부터 합치면 60+100+150=31060 + 100 + 150 = 310으로 더 비쌉니다.

예 2 — 어느 쪽 1을 먼저 100과 합쳐도 101+102=203101 + 102 = 203입니다. 양 끝의 1끼리는 이웃이 아니라서 먼저 합칠 수 없습니다.

예 3 — 이미 파일이 하나이므로 비용이 들지 않습니다.

효율성

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

함수 시그니처

solution(sizes: int[]) → long

제한 사항

  • 1≤N=1 \le N = sizes.length ≤3,000\le 3{,}000
  • 1≤1 \le sizes[i] ≤1,000,000\le 1{,}000{,}000
  • 답이 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를 합치는 것이므로

dp[i][j]=min⁡i≤k<j(dp[i][k]+dp[k+1][j])+S(i,j)dp[i][j] = \min_{i \le k < j} \big( dp[i][k] + dp[k+1][j] \big) + S(i, j)

입니다(S(i,j)S(i, j)는 구간 크기 합, 누적 합으로 O(1)O(1)). 그대로 계산하면 O(N3)O(N^3)이라 N=3000N = 3000에서는 너무 느립니다.

크누스 최적화

opt[i][j]를 최솟값을 주는 k라 하면, 이 비용 함수는 다음 성질을 만족합니다.

opt[i][j−1]≤opt[i][j]≤opt[i+1][j]opt[i][j-1] \le opt[i][j] \le opt[i+1][j]

그래서 k를 i..j-1 전체가 아니라 opt[i][j-1]..opt[i+1][j]에서만 찾으면 됩니다. 길이가 같은 구간들에 대해 탐색 범위의 합이 O(N)O(N)으로 망원(telescoping)되므로 전체 O(N2)O(N^2)입니다.

이 성질은 SS가 사각 부등식(S(a,c)+S(b,d)≤S(a,d)+S(b,c)S(a, c) + S(b, d) \le S(a, d) + S(b, c), a≤b≤c≤da \le b \le c \le d)과 단조성을 만족하기 때문에 성립합니다. 구간 합은 사각 부등식을 등호로 만족합니다.

복잡도 목표

O(N2)O(N^2)이 필요합니다. 모든 k를 시도하는 O(N3)O(N^3) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)236 ms추정
C++ (GCC, gnu++23)236 ms도출됨
Python 3.134714 ms도출됨
Java 251200 ms도출됨
Kotlin 2.4 (JVM)1472 ms추정
C# 14 (.NET 10)1472 ms추정

테스트 그룹

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

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