문제 개요
이 문제에서는 길이가 서로 다른 n개의 배열이 주어집니다. 우리의 목표는 길이가 m 이하인 최대 합 배열을 찾는 것입니다.
각 배열에서 부분 배열(subarray)을 선택하여 합을 최대화하되, 선택한 모든 부분 배열의 길이를 합쳤을 때 정확히 m이 되도록 만들어야 합니다.
예시를 통해 문제를 자세히 이해해 보겠습니다.
입력
n = 3, m = 4
arrOfArr[][] = {
{5, 2, -1, 4, -3}
{3, -2, 1, 6}
{-2, 0, 5}
}출력
20
설명
선택한 부분 배열은 {5, 4}, {6}, {5}
길이 = 2 + 1 + 1 = 4
합 = 5 + 4 + 6 + 5 = 20해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 먼저 DP 배열을 생성하고, 길이 k(0부터 m까지)에 대한 누적 합(cumulative sum)을 계산합니다.
2차원 DP 배열에는 각 배열별로 길이 0부터 m까지 모든 길이에 해당하는 최대 배열 합을 저장합니다. 이후 마지막 행에 기록된 값 중 가장 큰 값을 반환하면 그것이 곧 정답이 됩니다.
솔루션의 동작 과정을 보여주는 프로그램입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define N 5
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumArray(int arr[][N], int M) {
int DP[N][M];
int sumArray[M];
int sum[M];
memset(DP, -1, sizeof(DP[0][0]) * N * M);
sumArray[0] = 0;
DP[0][0] = 0;
for (int i = 1; i <= 5; i++) {
int len = arr[i - 1][0];
for (int j = 1; j <= len; j++) {
sumArray[j] = arr[i - 1][j];
sumArray[j] += sumArray[j - 1];
sum[j] = -100;
}
for (int j = 1; j <= len && j <= 6; j++)
for (int k = 1; k <= len; k++)
if (j + k - 1 <= len)
sum[j] = findMax(sum[j], sumArray[j + k - 1] - sumArray[k - 1]);
for (int j = 0; j <= 6; j++)
DP[i][j] = DP[i - 1][j];
for (int j = 1; j <= 6; j++)
for (int cur = 1; cur <= j && cur <= len; cur++)
DP[i][j] = findMax(DP[i][j], DP[i - 1][j - cur] + sum[cur]);
}
int maxSum = 0;
for (int i = 0; i <= 6; i++)
maxSum = findMax(maxSum, DP[5][i]);
return maxSum;
}
int main() {
int arr[][N] = { { 3, 2, -1, 6 },
{ 2, 7, -1 },
{ 3, 2, 2, -4 } };
int m = 4;
cout<<"Maximum sum array of length less than or equal to "<<m<<" : "<<findMaxSumArray(arr, m);
}실행 결과
Maximum sum array of length less than or equal to 4 : 15
정리
이처럼 동적 계획법을 활용하면 여러 개의 배열에서 조건에 맞는 부분 배열들을 조합하여 길이 제약(m 이하) 안에서 얻을 수 있는 최대 합을 체계적으로 구할 수 있습니다. 누적 합을 미리 계산해 두면 특정 구간의 합을 상수 시간에 구할 수 있어 전체 탐색 시간을 크게 줄일 수 있다는 점이 핵심입니다.