C++ 동적 계획법으로 연속된 세 요소마다 하나씩 선택할 때 최소 합 구하기

문제 개요

n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 이때 우리가 구해야 할 것은 배열 요소들의 최소 합이며, 단 하나의 조건이 붙습니다. 바로 연속된 세 개의 요소로 이루어진 구간마다 적어도 하나의 요소를 반드시 선택해야 한다는 것입니다.

예를 들어 배열이 [1, 2, 3, 6, 7, 1]이라면 출력은 4가 됩니다. 3과 1을 선택하면 3 + 1 = 4이기 때문입니다. 이 배열에서 확인해야 하는 연속 구간은 [1, 2, 3], [2, 3, 6], [3, 6, 7], [6, 7, 1]이며, 각 구간에서 하나씩 요소를 골랐음을 알 수 있습니다.

접근 방법: 동적 계획법(Dynamic Programming)

sum(i)를 "arr[i]가 해답에 포함되며 마지막으로 선택된 요소일 때 만들 수 있는 최소 합"이라고 정의해 봅시다. 그렇다면 최종 결과는 sum(n-1), sum(n-2), sum(n-3) 중 최솟값이 됩니다.

이 문제는 중복되는 하위 문제(Overlapping Subproblem) 구조를 가지므로, 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 점화식은 다음과 같습니다.

sum[i] = arr[i] + min(sum[i-1], sum[i-2], sum[i-3])

C++ 구현 예제

#include <iostream>
using namespace std;

int minOfThree(int a, int b, int c) {
    return min(min(a, b), c);
}

int getMinSum(int arr[], int n) {
    int sum[n];
    sum[0] = arr[0];
    sum[1] = arr[1];
    sum[2] = arr[2];
    for (int i = 3; i < n; i++)
        sum[i] = arr[i] + minOfThree(sum[i-3], sum[i-2], sum[i-1]);
    return minOfThree(sum[n-1], sum[n-2], sum[n-3]);
}

int main() {
    int arr[] = {1, 2, 3, 20, 2, 10, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum sum is: " << getMinSum(arr, n);
}

실행 결과

Minimum sum is: 4

코드 설명

getMinSum 함수는 DP 배열 sum을 사용해 각 인덱스까지 고려했을 때의 최소 합을 저장합니다. 처음 세 요소는 초기값으로 그대로 설정하고, 인덱스 3부터는 현재 요소 값에 바로 앞 세 개의 값 중 최솟값을 더해 나갑니다. 모든 계산이 끝나면 마지막 세 값 중 최솟값을 반환하는데, 이것이 조건을 만족하는 전체 최소 합입니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다.