[BOJ] 11985 오렌지 출하 - python

문제 링크 (opens new window)

문제 요약

주어진 조건을 만족하면서, 모든 오렌지를 포장하는 최소 비용을 구해라

문제 접근

DP[i] : i 번째 오렌지까지 포장했을때 최소 비용

i 번째 오렌지를 포함하는 현재 박스의 사이즈를 siz 라고 할때,

cost1 = (siz=1일때 박스 비용 + dp[i-1]),

cost2 = (siz=2 일때 박스 비용 + dp[i-2]),

...

costM = (siz=M 일때 박스 비용 + dp[i-M])

즉 DP[i] = (cost1~costM 중에 최솟값) 이라는 공식을 도출할수있다.

소스코드

PyPy3 로 제출했습니다.

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
MAX_A = 1000000000

# 1 <= i <= N
A = [0]+[int(input()) for _ in range(N)]

# dp[i] : i 번째 오렌지까지 포장했을때 최소 비용
dp = [0]*(N+1)
dp[1] = K

for i in range(2, N+1):
    min_v = max_v = A[i]
    
    dp[i] = dp[i-1]+K
    for siz in range(2, min(M, i)+1):
        # j: 포장하는 box 의 가장 왼쪽 오렌지 
        j = i - siz + 1 

        min_v, max_v = min(min_v, A[j]), max(max_v, A[j])
        
        box_cost = K+siz*(max_v-min_v)
        
        dp[i] = min(dp[i], dp[j-1]+box_cost)

print(dp[N])