파이썬으로 배열의 최소 조정 비용 구하기

문제 개요

양수로만 이루어진 배열이 주어졌다고 가정해 보겠습니다. 배열의 각 원소를 새로운 값으로 교체하여, 인접한 두 원소의 차이가 항상 주어진 target 값 이하가 되도록 만들어야 합니다. 이때 우리의 목표는 조정 비용, 즉 새 값과 기존 값의 차이의 절댓값 합을 최소화하는 것입니다.

수식으로 표현하면 ∑|A[i] − Anew[i]|를 최소화하는 문제이며, 여기서 i는 0부터 n−1까지의 범위입니다(n은 배열 A의 크기). Anew는 인접 원소 간 차이가 target 이하가 되도록 조정된 배열을 의미합니다.

예를 들어 입력이 [56, 78, 53, 62, 40, 7, 26, 61, 50, 48]이고 target = 20이라면, 출력은 35가 됩니다.

해결 접근 방식

이 문제는 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 각 원소의 값은 0부터 M(여기서는 100) 사이의 범위를 가진다고 가정하고, table[i][j]를 "i번째 원소를 j로 조정했을 때의 누적 최소 비용"으로 정의합니다. 전체 알고리즘은 다음과 같습니다.

• n := arr의 크기
• table := (n × (M+1)) 크기의 2차원 배열을 0으로 초기화
• j를 0부터 M까지 반복하며 table[0][j] := |j − arr[0]| 설정
• i를 1부터 n−1까지 반복:
  • j를 0부터 M까지 반복:
    • table[i][j] := 100000000 (무한대 초기화)
    • k를 max(j − target, 0)부터 min(M, j + target)까지 반복하며 table[i][j] := min(table[i][j], table[i−1][k] + |arr[i] − j|) 갱신
• ans := 10000000으로 초기화한 뒤, j를 0부터 M까지 반복하며 ans := min(ans, table[n−1][j]) 계산
• ans 반환

핵심 아이디어는 현재 원소를 값 j로 맞출 때, 이전 원소는 j ± target 범위 내의 어떤 값 k였어야 한다는 제약 조건입니다. 이 범위 안에서 이전 단계의 최소 비용을 참조하여 누적 비용을 계산함으로써 전체 최적해를 구할 수 있습니다.

예시 구현

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

M = 100

def get_min_cost(arr, target):
    n = len(arr)
    table = [[0 for i in range(M + 1)] for i in range(n)]
    for j in range(M + 1):
        table[0][j] = abs(j - arr[0])
    for i in range(1, n):
        for j in range(M + 1):
            table[i][j] = 100000000
            for k in range(max(j - target, 0), min(M, j + target) + 1):
                table[i][j] = min(table[i][j], table[i - 1][k] + abs(arr[i] - j))
    ans = 10000000
    for j in range(M + 1):
        ans = min(ans, table[n - 1][j])
    return ans

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

입력

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

출력

35

복잡도 분석

시간 복잡도는 각 원소마다 M개의 값과 최대 2×target+1개의 후보 값을 확인하므로 O(n × M × target)입니다. 공간 복잡도는 DP 테이블 저장에 O(n × M)이 필요합니다. 필요하다면 이전 행만 참조한다는 점을 활용해 공간을 O(M)까지 줄일 수 있습니다.