C++로 구현하는 부분 수열의 최대 합: 두 요소가 K 거리 미만에 위치하지 않도록 선택하기

이 문제에서는 크기가 n인 배열 arr[]와 정수 k가 주어집니다. 우리의 목표는 배열 내에서 두 요소가 서로 K 미만의 거리에 위치하지 않도록 선택한 부분 수열(subsequence)의 최대 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

즉, 선택하는 각 요소들이 서로 k 이상의 거리를 유지하도록 하면서, 그 합이 최대가 되는 부분 수열을 찾아야 합니다.

예제로 이해하기

입력

arr[] = {6, 2, 5, 1, 9, 11, 4}, k = 2

출력

16

설명

서로 k(=2) 이상 떨어져 있는 요소들로 만들 수 있는 모든 부분 수열:
{6, 1, 4} → 합 = 11
{2, 9} → 합 = 11
{5, 11} → 합 = 16
{1, 4} → 합 = 5
...
최대 합(maxSum) = 16

해결 접근 방식: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용해 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 배열의 현재 위치 i까지 고려했을 때 얻을 수 있는 최대 합을 DP[i]에 저장합니다. i번째 인덱스에서는 현재 요소 arr[i]를 부분 수열에 포함하는 것이 유리한지, 아니면 이전까지의 최대 합을 그대로 가져가는 것이 유리한지 판단합니다.

if (DP[i - (k+1)] + arr[i] > DP[i - 1])
    → DP[i] = DP[i - (k+1)] + arr[i]
그렇지 않으면
    → DP[i] = DP[i - 1]

여기서 DP[i - (k+1)]을 참조하는 이유는, 현재 요소 arr[i]와 함께 사용할 수 있는 가장 가까운 이전 요소가 (i - (k+1))번째 위치이기 때문입니다. 최종적으로 DP 배열 전체에서 가장 큰 값이 곧 최대 부분 수열의 합이 됩니다.

알고리즘 단계

초기화

maxSumSubSeq = -1, maxSumDP[n]

1단계

maxSumDP[0] = arr[0] 으로 초기화

2단계

i를 1부터 n-1까지 반복

2.1단계

i < k인 경우 → maxSumDP[i] = max(arr[i], maxSumDP[i-1])

2.2단계

그 외의 경우 → maxSumDP[i] = max(arr[i], maxSumDP[i-(k+1)] + arr[i])

3단계

maxSumDP의 모든 요소 중 최댓값을 찾아 maxSumSubSeq에 저장

4단계

maxSumSubSeq 반환

C++ 구현 예제

다음은 위 알고리즘의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;

int retMaxVal(int a, int b){
    if(a > b)
        return a;
    return b;
}

int calcMaxSumSubSeq(int arr[], int k, int n) {
    int maxSumDP[n];
    int maxSum = -1;
    maxSumDP[0] = arr[0];
    
    for (int i = 1; i < n; i++){
        if(i < k){
            maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i - 1]);
        }
        else
            maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i - (k + 1)] + arr[i]);
    }
    
    for(int i = 0; i < n; i++)
        maxSum = retMaxVal(maxSumDP[i], maxSum);
        
    return maxSum;
}

int main() {
    int arr[] = {6, 2, 5, 1, 9, 11, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    
    cout<<"두 요소가 "<<k<<" 미만의 거리에 나타나지 않는 부분 수열의 최대 합은 "
       <<calcMaxSumSubSeq(arr, k, n);
    return 0;
}

실행 결과

두 요소가 2 미만의 거리에 나타나지 않는 부분 수열의 최대 합은 16

마무리

이처럼 동적 계획법을 활용하면 각 위치에서 가능한 최적의 선택을 누적해 나가며 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다. 제약 조건이 있는 부분 수열 최적화 문제를 만났을 때, '현재 요소를 포함할지 말지'를 이전 상태와 비교하는 DP 사고방식을 기억해 두면 다양한 변형 문제에도 쉽게 적용할 수 있습니다.