C++로 구현하는 '인접하지 않은 요소' 최대 부분 수열 합 문제

이번 문제에서는 양수로만 구성된 크기 n의 배열 arr[]가 주어집니다. 목표는 배열에서 인접한 두 요소를 동시에 선택하지 않으면서 얻을 수 있는 최대 부분 수열 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

주어진 배열에서 여러 요소를 골라 합을 만들되, 특정 요소를 선택했다면 그 바로 옆에 있는(인접한) 요소는 선택할 수 없습니다. 이 제약 조건을 지키면서 만들 수 있는 합 중 최댓값을 찾는 것이 핵심입니다.

예시로 이해하기

입력

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

출력

설명

조건을 만족하는 선택 예시:
{5, 1, 6} → 합 = 5 + 1 + 6 = 12
{2, 9}   → 합 = 2 + 9 = 11
{5, 9}   → 합 = 5 + 9 = 14 ← 최댓값

위 예시에서 인덱스 0의 값 5와 인덱스 3의 값 9는 서로 인접하지 않으므로 동시에 선택할 수 있으며, 이때의 합 14가 최댓값이 됩니다.

해결 접근법: 동적 프로그래밍(DP)

이 문제는 동적 프로그래밍으로 효율적으로 해결할 수 있습니다. 각 위치마다 "현재 요소를 선택할지 건너뛸지"라는 두 가지 선택지만 존재하기 때문입니다.

크기가 n인 DP 배열 maxSumDP[]를 준비하고, maxSumDP[i]에는 i번째 인덱스부터 n-1까지의 범위에서 얻을 수 있는 최대 합을 저장합니다. 각 인덱스 i에서 고려해야 할 경우의 수는 다음과 같습니다.

현재 요소 arr[i]를 선택하는 경우: 인접한 요소는 선택할 수 없으므로, 그다음은 i+2 이후의 최적해를 더합니다. → arr[i] + maxSumDP[i+2]
현재 요소 arr[i]를 건너뛰는 경우: 다음 인덱스의 최적해를 그대로 사용합니다. → maxSumDP[i+1]

따라서 점화식은 아래와 같이 정리됩니다.

maxSumDP[i] = max(arr[i] + maxSumDP[i+2], maxSumDP[i+1])

알고리즘 단계

1단계 − 초기화:

maxSumDP[n-1] = arr[n-1]
maxSumDP[n-2] = max(arr[n-1], arr[n-2])

2단계 − 반복문 실행: i를 n-3부터 0까지 감소시키며 위 점화식대로 DP 테이블을 채웁니다.

maxSumDP[i] = max(arr[i] + maxSumDP[i+2], maxSumDP[i+1])

3단계 − 결과 반환: maxSumDP[0]이 전체 배열에 대한 최대 합이므로 이 값을 반환합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

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

int calcMaxSum(int arr[], int n){
    int maxSumDP[n];
    // 마지막 두 인덱스 초기화
    maxSumDP[n-1] = arr[n-1];
    maxSumDP[n-2] = retMaxVal(arr[n-1], arr[n-2]);
    // 뒤에서 앞으로 DP 테이블 채우기
    for (int i = n - 3; i >= 0; i--) {
        maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
            maxSumDP[i + 1]);
    }
    return maxSumDP[0];
}

int main() {
    int arr[] = { 5, 2, 1, 9, 6 };
    int n = sizeof(arr) / sizeof(int);
    cout << "인접한 두 요소를 선택하지 않을 때의 최대 부분 수열 합: "
         << calcMaxSum(arr, n);
    return 0;
}

실행 결과

인접한 두 요소를 선택하지 않을 때의 최대 부분 수열 합: 14

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(n) — DP 테이블을 위한 추가 배열이 필요합니다. 실제로는 이전 두 값만 참조하므로, 변수 두 개만 유지하면 O(1) 공간으로 최적화할 수도 있습니다.

C++로 구현하는 '인접하지 않은 요소' 최대 부분 수열 합 문제 - 동적 프로그래밍 접근법