[BOJ 11985] 오렌지 출하

https://www.acmicpc.net/problem/11985

11985번: 오렌지 출하

개수

- 문제 요약

 

Juicy Orange Industry(JOI)는 맛있는 오렌지를 포장해서 출하하는 것이 주된 업무인 회사이다.

JOI사에서는 수집한 N개의 오렌지를 상자에 넣어서 출하한다.

먼저, 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓아야 한다.

컨베이어 벨트 위에 놓여져있는 오렌지는 앞에서부터 순서대로 1부터 N까지 번호가 붙여져 있다.

i번째 오렌지의 크기는 Ai이다.

그다음 작업은 오렌지를 앞에서부터 순서대로 상자에 나눠서 넣는 것이다.

한 상자에 넣는 오렌지의 번호는 연속해야 하며, 최대 M개의 오렌지를 넣을 수 있다.

상자에 오렌지를 넣는 비용은 K + s × (a − b) 로 구할 수 있다.

여기서 a는 상자에 넣은 가장 큰 오렌지의 크기, b는 상자에 넣은 가장 작은 오렌지의 크기, s는 상자에 넣은 오렌지의 개수, K는 상자를 포장하는 비용이다.

컨베이어 벨트 위에 놓여져 있는 오렌지의 정보와, 한 상자에 넣을 수 있는 오렌지 개수의 최댓값, 상자를 포장하는 비용 K가 주어졌을 때, 모든 오렌지를 포장하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

dp[i] : i번째 오렌지까지 상자에 넣고 포장했을 때 드는 비용의 최솟값 

DP Table의 기본 값은 상자를 1개만 쓰는 경우로 세팅해 줍니다. (상자의 가격 * 오렌지 개수)

반복문을 돌려주며 오렌지 가격의 최소값을 계속 갱신해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 20001
typedef long long ll;
ll n,m,k,arr[MAX],dp[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		dp[i]=k*i;
	}
	for(int i=0;i<n;i++){
		ll mn=arr[i+1],mx=arr[i+1];
		for(int j=1;j<=m&&i+j<=n;j++){
			mn=min(mn,arr[i+j]);
			mx=max(mx,arr[i+j]);
			dp[i+j]=min(dp[i+j],dp[i]+k+j*(mx-mn));
		}
	}
	cout<<dp[n];
}

코드 제출 결과