Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 동적 계획법으로 최소 k 간격 요소를 포함하는 최대 합 부분 수열 구하기

문제 소개

이 문제에서는 크기가 n인 배열 arr[]과 숫자 k가 주어집니다. 목표는 배열에서 서로 최소 k만큼 떨어진(인덱스 간격이 k 이상인) 요소들로 구성된 부분 수열 중에서 합이 최대가 되는 값을 찾는 프로그램을 작성하는 것입니다.

문제 설명

주어진 배열에서 선택한 요소들의 인덱스가 서로 k 이상의 거리를 유지하도록 부분 수열을 구성하고, 가능한 모든 경우 중 합이 가장 큰 값을 구해야 합니다.

예제로 이해하기

입력

arr[] = {2, 3, 7, 9, 2, 8, 3}

출력

15

설명

조건을 만족하는 모든 부분 수열은 다음과 같습니다.
{2, 9, 3}, 합 = 14
{3, 2}, 합 = 5
{7, 8}, 합 = 15

이 중 최대 합은 {7, 8}의 15입니다.

해결 접근 방법

1. 완전 탐색(Brute Force)

가장 단순한 방법은 조건을 만족하는 모든 부분 수열을 생성하고, 각각의 합을 계산한 뒤 그중 최댓값을 반환하는 것입니다. 하지만 가능한 조합의 수가 급격히 늘어나므로 실제로는 비효율적입니다.

2. 동적 계획법(Dynamic Programming)

훨씬 효율적인 방법은 동적 계획법을 활용하는 것입니다. 현재 위치까지 고려한 최대 합을 DP 배열에 저장하고, 각 요소에 대해 두 가지 선택지를 비교해 더 큰 값을 취합니다.

  • 현재 요소를 합에 포함하는 경우: dp[i] = arr[i] + dp[i + k + 1]
  • 현재 요소를 합에서 제외하는 경우: dp[i] = dp[i + 1]

배열을 뒤에서부터 앞으로 순회하며 위 점화식을 적용하면, 마지막에 dp[0]에 전체 최대 합이 저장됩니다.

C++ 구현 예제

아래 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;

int calcMaxSubSeqSum(int arr[], int N, int k){
    int maxSumDP[N];
    maxSumDP[N - 1] = arr[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (i + k + 1 >= N)
            maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
        else
            maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
    }
    return maxSumDP[0];
}

int main() {
    int N = 10, k = 2;
    int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
    cout<<"The maximum sum subsequence with at-least k distant elements is "<<calcMaxSubSeqSum(arr, N, k);
    return 0;
}

실행 결과

The maximum sum subsequence with at-least k distant elements is 230

복잡도 및 마무리

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, DP 배열을 위해 O(N)의 추가 공간이 필요합니다. 완전 탐색 방식과 달리 입력 크기가 커져도 선형 시간 안에 답을 구할 수 있어, '최소 k 간격' 제약이 있는 최대 합 부분 수열 문제를 효율적으로 해결할 수 있습니다.