이 문제에서는 크기가 n인 배열 arr[]가 주어지며, 우리의 목표는 C++에서 동적 계획법(DP)을 활용하여 최대 합 증가 부분 수열(Maximum Sum Increasing Subsequence)을 찾는 프로그램을 작성하는 것입니다.
문제 설명
최대 합 증가 부분 수열이란, 배열에서 이전 원소보다 다음 원소가 항상 크다는 조건(증가 조건)을 만족하는 부분 수열 중에서 원소들의 합이 가장 큰 수열을 의미합니다.
예제로 이해하기
입력
arr[] = {4, 2, 3, 6, 5, 9}출력
20
설명
합이 최대인 증가 부분 수열:
{2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20위 예제에서 증가 조건을 만족하는 여러 부분 수열이 존재하지만, 그중 {2, 3, 6, 9}의 합인 20이 가장 큽니다.
풀이 접근 방식
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 각 인덱스 i에 대해, 해당 위치까지 만들 수 있는 최대 합을 저장하는 DP 배열(sumDP)을 생성합니다.
- 초기값은 각 원소 자신(arr[i])으로 설정합니다. 자기 자신만으로 이루어진 부분 수열의 합이기 때문입니다.
- i보다 앞에 있는 모든 j에 대해, arr[i] > arr[j]를 만족하면 sumDP[i]를 sumDP[j] + arr[i]와 비교하여 더 큰 값으로 갱신합니다.
- 마지막으로 sumDP 배열 전체에서 최댓값을 반환하면 정답이 됩니다.
시간 복잡도는 O(n²), 공간 복잡도는 O(n)입니다.
구현 예제
아래는 위 풀이 과정을 보여주는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
int retMaxVal(int x, int y){
if(x > y)
return x;
return y;
}
int calcMaxSubSeqSum(int arr[], int n) {
int maxSum = 0;
int sumDP[n];
// 초기화: 각 위치의 최소 합은 자기 자신
for (int i = 0; i < n; i++)
sumDP[i] = arr[i];
// DP 갱신: 증가 조건을 만족할 때 합을 누적
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if ((sumDP[i] < (sumDP[j] + arr[i])) && (arr[i] > arr[j]))
sumDP[i] = sumDP[j] + arr[i];
// 전체 최댓값 탐색
for (int i = 0; i < n; i++)
maxSum = retMaxVal(sumDP[i], maxSum);
return maxSum;
}
int main() {
int arr[] = {4, 2, 3, 6, 5, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"최대 합 증가 부분 수열의 합은 "
<<calcMaxSubSeqSum(arr, n);
return 0;
}출력 결과
최대 합 증가 부분 수열의 합은 20
정리
동적 계획법을 사용하면 가능한 모든 부분 수열을 일일이 확인하는 지수 시간(O(2ⁿ)) 대신, O(n²) 시간 안에 문제를 해결할 수 있습니다. 각 위치까지의 최대 합을 저장하고 재활용한다는 점이 DP의 핵심이며, 이는 LIS(최장 증가 부분 수열) 문제와 유사한 패턴입니다.