3개가 연속되지 않도록 하는 최대 부분 수열 합 구하기

이 튜토리얼에서는 세 개의 숫자가 연속으로 선택되지 않도록 하면서 최대 부분 수열 합을 구하는 프로그램을 다룹니다.

문제 설명

양의 정수로 이루어진 배열이 주어집니다. 우리의 목표는 임의의 세 숫자가 연속으로 포함되지 않는다는 조건을 지키면서, 부분 수열의 합이 최대가 되도록 만드는 것입니다.

예를 들어 배열 {1, 2, 3}에서는 세 숫자를 모두 더할 수 없으므로, {1, 2}, {2, 3}, {1, 3} 중 하나를 선택해야 합니다.

접근 방식: 동적 계획법

이 문제는 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. sum[i]를 'i번째 원소까지 고려했을 때의 최대 합'이라고 정의하면, 각 위치에서 아래 세 가지 선택지 중 최댓값을 취합니다.

• i번째 원소를 건너뛰는 경우: sum[i-1]
• i번째 원소 하나만 포함하는 경우(i-1은 제외): sum[i-2] + arr[i]
• i번째와 i-1번째 원소를 함께 포함하는 경우(i-2는 제외): arr[i] + arr[i-1] + sum[i-3]

점화식으로 정리하면 다음과 같습니다.
sum[i] = max(sum[i-1], sum[i-2] + arr[i], arr[i] + arr[i-1] + sum[i-3])

초기값 설정

• n ≥ 1일 때: sum[0] = arr[0]
• n ≥ 2일 때: sum[1] = arr[0] + arr[1]
• n > 2일 때: sum[2] = max(sum[1], arr[1] + arr[2], arr[0] + arr[2])

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 세 개의 연속된 숫자를 포함하지 않는
// 최대 부분 수열 합을 반환
int maxSumWO3Consec(int arr[], int n) {
    int sum[n];
    if (n >= 1) sum[0] = arr[0];
    if (n >= 2) sum[1] = arr[0] + arr[1];
    if (n > 2) sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]));
    for (int i = 3; i < n; i++)
        sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]), arr[i] + arr[i - 1] + sum[i - 3]);
    return sum[n - 1];
}
int main() {
    int arr[] = { 100, 1000 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSumWO3Consec(arr, n);
    return 0;
}

실행 결과

1100

배열 {100, 1000}은 크기가 2이므로 '세 개 연속 금지' 조건에 걸리지 않고 두 원소를 모두 선택할 수 있습니다. 따라서 최대 합은 100 + 1000 = 1100이 됩니다.