문제 소개
이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어지며, 배열의 첫 번째 원소에서 시작하는 최대 합 교대 부분 수열(Maximum Sum Alternating Subsequence)을 찾는 프로그램을 작성해야 합니다.
교대 부분 수열(alternating subsequence)이란 원소들이 감소와 증가를 번갈아 가며 나타나는 부분 수열을 말합니다. 즉, 먼저 감소한 뒤 다시 증가하고, 다시 감소하는 형태를 이룹니다. 단, 증가부터 시작하는 역방향 교대 부분 수열은 최대 합을 구할 때 유효하지 않습니다.
예제를 통해 문제를 이해해 보겠습니다.
입력
arr[] = {5, 1, 6, 2, 4, 8, 9}
출력
27
설명
시작 원소: 5, 감소: 1, 증가: 6, 감소: 2, 증가: 4 이후에는 4, 8, 9 중 하나를 부분 수열의 마지막 원소로 활용할 수 있습니다. 합 = 5 + 1 + 6 + 2 + 4 + 9 = 27
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 이용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 개의 DP 배열을 사용하는 것입니다.
- maxSumInc[i]: arr[i]로 끝나며 마지막 이동이 '증가'인 교대 부분 수열의 최대 합
- maxSumDec[i]: arr[i]로 끝나며 마지막 이동이 '감소'인 교대 부분 수열의 최대 합
배열의 원소를 하나씩 추가하면서 해당 원소가 교대 부분 수열을 이루는지 확인하고, 각 인덱스까지의 최대 합을 계산합니다. 모든 n개의 원소를 순회한 후, 두 배열에서 얻을 수 있는 값들 중 최댓값을 반환하면 됩니다. 이 방법의 시간 복잡도는 O(n²), 공간 복잡도는 O(n)입니다.
예제 코드
솔루션의 동작을 보여주는 프로그램입니다.
#include<iostream>
#include<cstring>
using namespace std;
int maxVal(int x, int y){
if(x > y)
return x;
return y;
}
int calcMaxSumAltSubSeq(int arr[], int n) {
int maxSum = -10000;
int maxSumDec[n];
bool isInc = false;
memset(maxSumDec, 0, sizeof(maxSumDec));
int maxSumInc[n];
memset(maxSumInc, 0, sizeof(maxSumInc));
maxSumDec[0] = maxSumInc[0] = arr[0];
for (int i=1; i<n; i++) {
for (int j=0; j<i; j++) {
if (arr[j] > arr[i]) {
maxSumDec[i] = maxVal(maxSumDec[i],
maxSumInc[j]+arr[i]);
isInc = true;
}
else if (arr[j] < arr[i] && isInc)
maxSumInc[i] = maxVal(maxSumInc[i],
maxSumDec[j]+arr[i]);
}
}
for (int i = 0 ; i < n; i++)
maxSum = maxVal(maxSum, maxVal(maxSumInc[i],
maxSumDec[i]));
return maxSum;
}
int main() {
int arr[]= {8, 2, 3, 5, 7, 9, 10};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum sum alternating subsequence starting is "<<calcMaxSumAltSubSeq(arr , n);
return 0;
}
출력
The maximum sum alternating subsequence starting is 25
위 코드에서 배열 {8, 2, 3, 5, 7, 9, 10}에 대해 계산된 최대 합 교대 부분 수열의 합은 25입니다. 이처럼 두 개의 DP 배열을 활용하면 증가와 감소 상태를 명확하게 추적하면서 문제를 체계적으로 해결할 수 있습니다.