문제 설명
배열 하나와 두 개의 숫자 M, K가 주어졌을 때, 크기가 K인 M개의 부분 배열 중 서로 겹치지 않으면서 합이 최대가 되는 조합을 찾아야 합니다. 단, 배열 내 요소들의 순서는 그대로 유지되어야 합니다.
여기서 K는 각 부분 배열의 크기를, M은 선택할 부분 배열의 개수를 의미합니다. 배열의 전체 크기는 M×K보다 크다고 가정할 수 있으며, 만약 배열의 길이가 K의 배수가 아니라면 마지막 부분 배열은 일부만 잘라서 사용할 수 있습니다.
예시
주어진 배열이 {2, 10, 7, 18, 5, 33, 0}이고 N = 7, M = 3, K = 1이라고 가정해 보겠습니다. 이 경우 출력값은 61이며, 선택된 부분 배열은 다음과 같습니다.
{33, 18, 10}알고리즘
- 접두사 합(Prefix Sum) 배열 생성: 각 인덱스 i에 대해 원본 배열에서 i번째부터 i+K-1번째까지 K개 요소의 합을 저장합니다. 이 배열의 크기는 n+1-k가 됩니다.
- 부분 배열을 포함하는 경우: 크기가 k인 부분 배열을 선택하면, 해당 부분 배열에 속한 요소들은 다른 부분 배열에 다시 사용할 수 없습니다(겹침 방지). 따라서 선택된 부분 배열의 k개 요소를 건너뛰고(start + k 위치부터) 재귀 호출을 진행합니다.
- 부분 배열을 제외하는 경우: 현재 위치의 부분 배열을 선택하지 않으면, 그 부분 배열의 나머지 k-1개 요소는 다른 부분 배열에서 활용할 수 있습니다. 따라서 첫 번째 요소만 건너뛰고(start + 1 위치부터) 재귀 호출을 진행합니다.
- 최댓값 반환: 마지막으로 max(포함한 경우의 합, 제외한 경우의 합) 중 더 큰 값을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
presum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++) {
presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
}
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
if (m == 0)
return 0;
if (start > size - 1)
return 0;
int mx = 0;
int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
return max(includeMax, excludeMax);
}
int main() {
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
return 0;
}
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
Maximum sum = 61