C++로 해결하는 최대 부분 수열 합 문제 – 세 요소 연속 선택 금지 조건

문제 개요

이 문제에서는 n개의 양의 정수로 이루어진 배열 arr[]가 주어집니다. 우리가 작성해야 할 프로그램은 세 개의 요소가 연속적으로 선택되지 않도록 하는 조건을 지키면서 얻을 수 있는 최대 부분 수열 합을 찾는 것입니다.

여기서 연속적인(consecutive) 요소란 배열에서 인덱스 순서를 그대로 따르는 요소들을 의미합니다. 예를 들어 다음과 같은 형태입니다.

arr[0], arr[1], arr[2], …

즉, 부분 수열을 구성할 때 arr[i], arr[i+1], arr[i+2]처럼 세 요소를 모두 골라 담는 일만 없으면 되고, 두 요소까지 연속으로 선택하는 것은 허용됩니다.

입력 · 출력 예시

입력:

arr[] = {5, 9, 12, 15}

출력:

설명:

합 = 5 + 12 + 15 = 32

9를 건너뛰고 5, 12, 15를 선택하면 세 요소가 모두 연속인 경우가 없으므로 조건을 만족하면서 최대 합 32를 얻을 수 있습니다.

해결 접근 방법

가장 효율적인 방법은 동적 계획법(Dynamic Programming)을 활용하는 것입니다. 각 인덱스까지의 최대 합을 저장하는 보조 배열을 만들고, 현재 위치에서 가능한 선택지를 비교하며 값을 채워 나갑니다.

첫 두 값은 연속 세 개 조건이 성립할 수 없으므로 다음과 같이 초기화합니다.

sumVal[0] = arr[0]
sumVal[1] = arr[0] + arr[1]

세 번째 요소부터는 단순히 더할 수 없으며, 직전 요소들과의 관계를 고려해야 합니다.

arr[i]를 포함했을 때 합이 더 커진다면, arr[i−1] 또는 arr[i−2] 중 하나를 제외한 상태에서 포함합니다.
포함해도 이득이 없다면 arr[i]를 제외하고 기존 합을 그대로 유지합니다.

이 논리를 점화식으로 정리하면 다음과 같습니다.

sum[i] = max(sum[i−3] + arr[i−1] + arr[i],
            sum[i−2] + arr[i],
            sum[i−1])

각 항의 의미는 다음과 같습니다.

sum[i−3] + arr[i−1] + arr[i]: arr[i−2]를 건너뛰고 마지막 두 요소를 함께 선택하는 경우
sum[i−2] + arr[i]: arr[i−1]을 건너뛰고 arr[i]만 추가로 선택하는 경우
sum[i−1]: arr[i]를 아예 선택하지 않는 경우

이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(n)입니다.

C++ 구현 코드

#include <iostream>
using namespace std;

int findMaxSubSeqSum(int arr[], int n) {
    int maxSumArr[n];
    maxSumArr[0] = arr[0];
    maxSumArr[1] = arr[0] + arr[1];
    maxSumArr[2] = max(maxSumArr[1], max(arr[1] + arr[2], arr[0] + arr[2]));
    for (int i = 3; i < n; i++) {
        int sum1 = maxSumArr[i - 2] + arr[i];
        int sum2 = arr[i] + arr[i - 1] + maxSumArr[i - 3];
        maxSumArr[i] = max(max(maxSumArr[i - 1], sum1), sum2);
    }
    return maxSumArr[n - 1];
}

int main() {
    int arr[] = { 5, 9, 12, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum subsequence sum such that no three are consecutive is "
         << findMaxSubSeqSum(arr, n);
    return 0;
}

실행 결과

The maximum subsequence sum such that no three are consecutive is 32

정리

이 문제는 '집의 도난(House Robber)' 유형과 같은 대표적인 동적 계획법 응용 문제입니다. 핵심은 각 위치에서 현재 요소를 선택할지 말지를 판단할 때, 직전 두 개의 선택 상태를 함께 고려한다는 점입니다. 보조 배열에 누적 최댓값을 저장해 두면 한 번의 순회만으로 정답을 구할 수 있어 입력 크기가 커져도 효율적으로 동작합니다.