이 튜토리얼에서는 C++를 이용해 배열에서 두 요소가 서로 K 미만의 거리에 놓이지 않도록 선택할 때, 만들 수 있는 부분 수열의 최대 합을 구하는 프로그램을 다룹니다.
문제의 조건은 다음과 같습니다. N개의 정수로 이루어진 배열과 값 K가 주어지며, 우리는 서로의 인덱스 거리가 충분히 떨어진 요소들만 포함하는 부분 수열 중에서 합이 가장 큰 경우를 찾아야 합니다.
접근 방법: 동적 계획법(Dynamic Programming)
이 문제는 동적 계획법을 사용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- dp[i]: i번째 원소까지 고려했을 때 얻을 수 있는 최대 합을 저장합니다.
- i ≤ k인 경우: dp[i] = max(arr[i], dp[i-1]) — 거리 제한 조건 때문에 k 이내 범위에서는 사실상 하나의 원소만 선택할 수 있으므로, 현재 원소와 이전까지의 최대 합 중 큰 값을 취합니다.
- i > k인 경우: dp[i] = max(arr[i], dp[i-(k+1)] + arr[i]) — 현재 원소를 새로 시작하거나, 최소 k+1만큼 떨어져 있는 이전 상태의 최대 합에 현재 원소를 더합니다.
최종 정답은 dp 배열 전체 요소 중 최댓값이 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 최대 합을 반환하는 함수
int maxSum(int* arr, int k, int n) {
if (n == 0)
return 0;
if (n == 1)
return arr[0];
if (n == 2)
return max(arr[0], arr[1]);
int dp[n];
dp[0] = arr[0];
for (int i = 1; i <= k; i++)
dp[i] = max(arr[i], dp[i - 1]);
for (int i = k + 1; i < n; i++)
dp[i] = max(arr[i], dp[i - (k + 1)] + arr[i]);
int max = *(std::max_element(dp, dp + n));
return max;
}
int main() {
int arr[] = { 6, 7, 1, 3, 8, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << maxSum(arr, k, n);
return 0;
}
출력 결과
15
동작 과정 살펴보기
예제 입력 배열 {6, 7, 1, 3, 8, 2, 4}와 k = 2를 기준으로 DP 테이블이 채워지는 과정은 다음과 같습니다.
- dp[0] = 6
- dp[1] = max(7, 6) = 7
- dp[2] = max(1, 7) = 7
- dp[3] = max(3, dp[0] + 3) = max(3, 9) = 9
- dp[4] = max(8, dp[1] + 8) = max(8, 15) = 15
- dp[5] = max(2, dp[2] + 2) = max(2, 9) = 9
- dp[6] = max(4, dp[3] + 4) = max(4, 13) = 13
따라서 최종 결과는 15이며, 이는 인덱스 1의 값 7과 인덱스 4의 값 8을 선택한 부분 수열의 합입니다. 두 요소의 인덱스 차이는 3으로 조건을 만족합니다.
마무리
이처럼 동적 계획법을 활용하면 거리 제약이 있는 부분 수열의 최대 합 문제를 효율적으로 해결할 수 있습니다. 시간 복잡도와 공간 복잡도 모두 O(n)으로, 배열의 크기가 커져도 안정적인 성능을 기대할 수 있습니다.