C++로 배열의 최소 조정 비용 구하기 (동적 계획법 풀이)

개념

양의 정수로 이루어진 배열이 주어졌을 때, 배열의 각 요소를 교체하여 인접한 요소 간의 차이가 주어진 target 값 이하가 되도록 만들어야 합니다. 이때 목표는 조정 비용(adjustment cost), 즉 새로운 값과 기존 값의 차이의 합을 최소화하는 것입니다.

다시 말해, Σ|A[i] – A_new[i]| (단, 0 ≤ i ≤ n-1)를 최소화해야 하며, 여기서 n은 배열 A[]의 크기, A_new[]는 인접 요소 간 차이가 target 이하가 되도록 조정된 배열을 의미합니다. 편의상 배열의 모든 요소는 상수 M = 100보다 작다고 가정합니다.

입력 예시

arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20

출력 예시

Minimum adjustment cost is 35

풀이 방법: 동적 계획법(DP)

조정 비용 Σ|A[i] – A_new[i]|를 최소화하려면 모든 인덱스 i에 대해 |A[i] – A_new[i]|가 0에 최대한 가까워야 합니다. 동시에 다음 제약 조건도 반드시 만족해야 합니다.

|A[i] – A_new[i+1]| ≤ Target

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. dp1[i][j]를 'A[i]를 값 j로 변경했을 때의 최소 조정 비용'이라고 정의하면, 점화식은 다음과 같습니다.

dp1[i][j] = min{dp1[i - 1][k]} + |j - A[i]|

여기서 k는 |k - j| ≤ target을 만족하는 모든 값입니다. 즉, 0 ≤ i ≤ n, 0 ≤ j ≤ M(n은 배열의 요소 개수, M = 100)일 때, k는 max(j – target, 0) ≤ k ≤ min(M, j + target) 범위의 값을 모두 고려합니다. 최종적으로 배열의 최소 조정 비용은 0 ≤ j ≤ M 범위에서 min{dp1[n – 1][j]}가 됩니다.

C++ 예제 코드

// 배열의 최소 조정 비용을 구하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
#define M1 100

// 배열의 최소 조정 비용을 구하는 함수
int minAdjustmentCost(int A1[], int n1, int target1) {
    // dp1[i][j]: A1[i]를 j로 변경할 때의 최소 조정 비용 저장
    vector<vector<int>> dp1(n1, vector<int>(M1 + 1));

    // 배열의 첫 번째 요소는 별도로 처리
    for (int j = 0; j <= M1; j++)
        dp1[0][j] = abs(j - A1[0]);

    // 나머지 요소들에 대해 반복 수행
    for (int i = 1; i < n1; i++) {
        // A1[i]를 j로 교체하고 최소 조정 비용 dp1[i][j]를 계산
        for (int j = 0; j <= M1; j++) {
            // 최소 조정 비용을 INT_MAX로 초기화
            dp1[i][j] = INT_MAX;
            // k >= max(j - target1, 0)이고 k <= min(M1, j + target1)인
            // 모든 k를 고려하여 최솟값을 선택
            for (int k = max(j - target1, 0); k <= min(M1, j + target1); k++)
                dp1[i][j] = min(dp1[i][j], dp1[i - 1][k] + abs(A1[i] - j));
        }
    }

    // dp 테이블의 마지막 행에서 최솟값을 반환
    int res1 = INT_MAX;
    for (int j = 0; j <= M1; j++)
        res1 = min(res1, dp1[n1 - 1][j]);
    return res1;
}

// 위 함수들을 테스트하는 드라이버 프로그램
int main() {
    int arr1[] = {56, 78, 53, 62, 40, 7, 26, 61, 50, 48};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int target1 = 20;
    cout << "Minimum adjustment cost is "
         << minAdjustmentCost(arr1, n1, target1) << endl;
    return 0;
}

실행 결과

Minimum adjustment cost is 35

복잡도 분석

시간 복잡도: O(n × M × target) — 각 요소마다 j(최대 M+1개)와 k(최대 2×target+1개)를 모두 탐색하기 때문입니다.
공간 복잡도: O(n × M) — dp 테이블 전체를 저장합니다. 이전 행만 참조하므로, 두 개의 1차원 배열만 사용하면 공간을 O(M)까지 줄일 수 있습니다.