백준 11985번, 오렌지 출하 풀이

문제

백준 11985번

풀이

점화식: $ dp[i] = i번째\ 오렌지까지\ 담았을\ 때\ 드는\ 최소의\ 비용 $ 으로 두었을 때, $ i $번째 오렌지에 대해서 $ k ( 1 \le k \le n) $개만큼 한 상자에 담는 경우를 처리하면서 dp table을 채워줍시다.

 

자세한 설명은 코드에서 이어가겠습니다.

이해안되거나 질문 있으시면 댓글 남겨주세요.

 

정답은 $ dp[n] $에 들어간 값이 됩니다.

 

모든 $ i (1 \le i \le n) $에 대해서 $ n $번 방문하니 시간복잡도는 $ O(n^2) $이 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

ull orange[20001], dp[20001];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	ull n, m, k; cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> orange[i];
        
    	//기본적으로 1개의 상자만 사용하는 경우 가격은 상자 비용 * 개수만큼 됩니다.
		dp[i] = k * i;
	}

	for (int i = 0; i < n; i++) {
    	//담을 오렌지의 최솟값, 최댓값을 저장하는 변수
		ull min_v = orange[i + 1], max_v = orange[i + 1];
        
    	//변수 j는 오렌지를 담을 개수
		for (int j = 1; j <= m && i + j <= n; j++) {
			min_v = min(min_v, orange[i + j]); //최솟값 갱신
			max_v = max(max_v, orange[i + j]); //최댓값 갱신
            
    		//기존에 있던 dp[i + j]보다 dp[i]에서 j개만큼
    		//새로 담은 경우의 가격이 적은 경우 dp table을 갱신
			dp[i + j] = min(dp[i + j], dp[i] + k + j * (max_v - min_v));
		}
	}
	cout << dp[n];
}