묶음 합의 제곱합 최소로 나누기

레벨 MC · 코딩 · JavaScript · 목표 시간 45분 · 게시일 2026-11-04

양의 정수 배열 nums를 순서를 바꾸지 않고 정확히 k개의 비어 있지 않은 연속 구간으로 나눈다. 각 구간의 원소 합을 제곱해 모두 더한 값을 비용이라 할 때, 비용의 최솟값을 구하시오.

nums의 길이 n은 최대 4,000, 각 원소는 1 이상 1,000 이하, k는 1 이상 min(n, 100) 이하이다. 구간마다 모든 나눔 위치를 따지는 O(k·n²) 방법으로는 시간 안에 끝나지 않는다.

예제

solve([1,2,3,4,5], 2)
solve([7,7,7], 3)
solve([4,1], 1)