C++로 정수 배열을 하나의 값으로 병합하는 최소 비용 구하기

양의 정수 n개가 담긴 배열 arr와 정수 j가 주어졌다고 가정해 봅시다. 우리가 수행해야 할 작업은 j개의 숫자를 골라 더하여 하나의 값으로 병합하는 것이며, 병합 비용은 선택한 j개 숫자의 합과 같습니다. 목표는 이러한 병합 연산에 드는 최소 비용을 구하는 것입니다.

문제 이해하기

예를 들어 입력이 arr = [2, 5, 6, 2, 3, 1, 3], j = 4라면 출력은 31이 됩니다.

먼저 2, 3, 1, 3을 병합하면 비용은 2 + 3 + 1 + 3 = 9입니다.

병합 후 배열은 [2, 5, 6, 9]가 됩니다. 두 번째 병합 연산의 비용은 2 + 5 + 6 + 9 = 22입니다. 따라서 전체 병합 비용은 22 + 9 = 31이 되며, 이것이 가능한 최소 병합 비용입니다.

접근 방법

이 문제는 구간 동적 계획법(Interval DP)으로 해결할 수 있습니다. 핵심 아이디어는 길이가 k인 구간을 작은 부분 구간들로 나누어 각각의 최소 비용을 조합하는 것입니다. 해결 절차는 다음과 같습니다.

n := arr의 크기로 설정합니다.
(n - 1) mod (j - 1)이 0이 아니라면 -1을 반환합니다. (j개씩 묶어 하나로 만들 수 없는 경우)
접두사 합을 저장할 배열 temp(n + 1)을 정의합니다.
i를 n - 1부터 0까지 감소시키며 temp[i] := arr[i] + temp[i + 1]을 계산합니다.
n x n 크기의 2차원 배열 dynArr을 정의합니다.
k를 j부터 n까지 증가시키며 다음을 반복합니다.
- le := 0, rg := k - 1에서 시작해 rg < n인 동안 le과 rg를 1씩 증가시키며 반복합니다.
  - dynArr[le][rg] := 무한대(INF)로 초기화합니다.
  - i를 le부터 rg 미만까지 (j - 1)씩 증가시키며 dynArr[le][rg] := min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg])로 갱신합니다.
  - (rg - le) mod (j - 1)이 0이라면 dynArr[le][rg] += temp[le] - temp[rg + 1]을 더해 실제 병합 비용을 반영합니다.
최종적으로 dynArr[0][n - 1]을 반환합니다.

C++ 구현 예제

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int j) {
    int n = arr.size();
    if ((n - 1) % (j - 1) != 0) return -1;

    vector<int> temp(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        temp[i] = arr[i] + temp[i + 1];
    }
    vector<vector<int>> dynArr(n, vector<int>(n));
    for (int k = j; k <= n; k++) {
        for (int le = 0, rg = k - 1; rg < n; le++, rg++) {
            dynArr[le][rg] = INT_MAX;
            for (int i = le; i < rg; i += j - 1) {
                dynArr[le][rg] = min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg]);
            }
            if ((rg - le) % (j - 1) == 0) {
                dynArr[le][rg] += temp[le] - temp[rg + 1];
            }
        }
    }
    return dynArr[0][n - 1];
}

int main() {
    vector<int> arr = {2, 5, 6, 2, 3, 1, 3};
    cout << solve(arr, 4) << endl;
    return 0;
}

입력

{2, 5, 6, 2, 3, 1, 3}, 4

출력

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n³)이며, 2차원 DP 테이블과 접두사 합 배열을 사용하므로 공간 복잡도는 O(n²)입니다. 구간의 길이를 k로 늘려가며 부분 구간의 최솟값을 결합하는 방식 덕분에 모든 병합 순서를 일일이 시도하지 않고도 최소 비용을 효율적으로 찾을 수 있습니다.