C++ 배열 최대 평균 합 분할 문제: 메모이제이션 DP로 풀기

문제 정의

주어진 배열 A를 최대 K개의 인접한(비어 있지 않은) 그룹으로 분할한다고 가정해 봅시다. 이때 점수는 각 그룹의 평균값을 모두 더한 값이 됩니다. 우리가 구해야 할 것은 이러한 분할 방식 중에서 얻을 수 있는 최대 점수입니다.

예시

입력 배열이 {9, 2, 5, 3, 10}이고 K = 3이라면, 다음과 같이 세 그룹으로 나눌 수 있습니다.

{9}, {2, 5, 3}, {10}

이 분할에 대한 평균의 합은 다음과 같이 계산됩니다.

9 + (2 + 5 + 3) / 3 + 10 = 22.33

접근 방법: 메모이제이션 활용

이 문제는 동적 계획법(DP)과 메모이제이션 기법을 사용하면 효율적으로 해결할 수 있습니다.

• memo[i][k]를 “배열 A[i..n-1]을 최대 K개 그룹으로 나눌 때 얻을 수 있는 최대 점수”라고 정의합니다.
• 첫 번째 그룹을 결정할 때는 A[i..n-1]을 A[i..j-1]과 A[j..n-1] 두 부분으로 나눕니다. 이 경우 후보 점수는 average(i, j) + score(j, k-1)이며, 여기서 average(i, j) = (A[i] + A[i+1] + … + A[j-1]) / (j - i)입니다. 가능한 모든 j에 대해 계산한 뒤 가장 높은 값을 선택합니다.
• 일반적인 경우의 재귀 관계식은 다음과 같습니다.
  memo[n][k] = max(memo[n][k], score(n, arr, k-1) + average(i, j))

C++ 구현 예제

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

double memo[MAX][MAX];

double score(int n, vector<int>& arr, int k) {
    if (memo[n][k] > 0) {
        return memo[n][k];
    }
    double sum = 0;
    for (int i = n - 1; i > 0; i--) {
        sum += arr[i];
        memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i));
    }
    return memo[n][k];
}

double getLargestSum(vector<int>& arr, int K) {
    int n = arr.size();
    double sum = 0;
    memset(memo, 0.0, sizeof(memo));
    // 기저 사례: 그룹이 1개일 때는 구간 전체의 평균이 곧 최대 점수
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        memo[i + 1][1] = sum / (i + 1);
    }
    return score(n, arr, K);
}

int main() {
    vector<int> arr = {9, 2, 5, 3, 10};
    int K = 3;
    cout << "Largest sum = " << getLargestSum(arr, K) << endl;
    return 0;
}

코드 설명

• score() 함수는 이미 계산된 값이 메모 배열에 저장되어 있다면 즉시 반환하여 중복 연산을 방지합니다.
• getLargestSum() 함수는 k = 1인 경우(그룹이 하나뿐인 상황)의 기저 사례를 미리 채워 둡니다. 그룹이 하나면 구간 전체의 단순 평균이 곧 최대 점수가 되기 때문입니다.
• 전체 시간 복잡도는 O(n² × K), 공간 복잡도는 O(n × K)입니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Largest sum = 22.3333