문제 개요
숫자로 이루어진 리스트 nums와 정수 k가 주어집니다. 이때 서로 겹치지 않으면서 비어 있지 않은 k개의 부분 리스트(연속된 구간)를 선택하여, 각 부분 리스트 합의 총합이 최대가 되도록 만들어야 합니다. 단, k는 nums의 크기보다 작거나 같다고 가정합니다.
예를 들어 입력이 nums = [11, -1, 2, 1, 6, -24, 11, -9, 6]이고 k = 3이라면 출력은 36이 됩니다. [11, -1, 2, 1, 6], [11], [6] 세 구간을 선택하면 각각의 합이 19, 11, 6이 되어 총합 36을 얻을 수 있습니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 두 개의 상태 배열을 활용합니다.
- hi[i] : 지금까지 살펴본 원소들로 i개의 부분 리스트를 완성했을 때 얻을 수 있는 최대 합
- open[i] : i번째 부분 리스트가 현재 열려 있는(계속 확장 중인) 상태일 때의 최대 합
두 배열의 초기값은 음의 무한대(-inf)로 설정하고, hi[0]만 0으로 초기화합니다. 이후 nums의 각 원소를 하나씩 순회하면서 상태를 갱신합니다.
알고리즘 단계
- n := nums의 크기
- n이 0이거나 k가 0이면 0을 반환
- 크기가 k + 1인 배열 hi와 open을 선언하고 모두 -inf로 채우기
- hi[0] := 0
- nums의 각 원소 num에 대해 다음을 반복:
- 크기가 k + 1인 새 배열 nopen을 선언하고 -inf로 채우기
- i를 1부터 k까지 증가시키며 반복:
- open[i] > -inf이면 nopen[i] := open[i] + num (현재 열린 구간을 계속 확장)
- hi[i - 1] > -inf이면 nopen[i] := max(nopen[i], hi[i - 1] + num) (새로운 구간 시작)
- open := move(nopen)
- i를 1부터 k까지 증가시키며 hi[i] := max(hi[i], open[i])로 갱신
- hi[k] 반환
C++ 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0 || k == 0)
return 0;
vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
hi[0] = 0;
for (int num : nums) {
vector<int> nopen(k + 1, INT_MIN);
for (int i = 1; i <= k; ++i) {
if (open[i] > INT_MIN)
nopen[i] = open[i] + num;
if (hi[i - 1] > INT_MIN)
nopen[i] = max(nopen[i], hi[i - 1] + num);
}
open = move(nopen);
for (int i = 1; i <= k; ++i)
hi[i] = max(hi[i], open[i]);
}
return hi[k];
}
int main(){
vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
int k = 3;
cout << solve(v, 3);
}
입력
{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3
출력
36
복잡도 분석
시간 복잡도는 O(n × k)이며, 공간 복잡도는 O(k)입니다. 각 원소를 처리할 때마다 k개의 상태만 유지하므로, 입력 크기가 커져도 메모리 사용량은 일정하게 유지됩니다.