오렌지 출하 > 문제은행



문제은행

3155 : 오렌지 출하

제한시간: 2000 ms    메모리제한: 512 MB
해결횟수: 29 회    시도횟수: 140 회   



당신은 Juicy Orange Industry 사를 알고 있는가? 이 회사의 업무는 맛있는 오렌지를 포장해서 출하하는 것이다. 여기서는 줄여서 JOI사라고 부르겠다.

 

JOI사에서는 수집된 N개의 오렌지를 상자에 넣어 출하하게 되었다. 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓여져서, 컨베이어 벨트 앞에서부터 순서대로 1부터 N까지 번호가 붙여져 있다. 오렌지는 크기가 제각각이어서, 오렌지 i(1iN)의 크기를 Ai라 한다.

 

이 오렌지들을 앞에서부터 순서대로 몇 개를 상자에 나눠 담는다. 한 상자에는 연속한 번호의 오렌지밖에 담을 수 없다.

 

, 하나의 상자에는 최대 M개까지 오렌지를 담을 수 있다. 어떤 상자에 몇 개의 오렌지를 담을 때 드는 비용은, 상자에 담긴 가장 큰 오렌지의 크기를 a, 상자에 담긴 가장 작은 오렌지의 크기를 b, 상자에 담긴 오렌지의 개수를 s라고 할 때, K+s*(a-b)로 구할 수 있다. 여기에서 K는 상자를 포장하는 비용으로, 모든 상자에 똑같이 적용된다.

 

적절한 개수의 상자를 사용해서 모든 오렌지를 적절하게 포장할 때, 상자 포장에 드는 비용의 총합을 가능한 한 작게 하고 싶다.

 

오렌지 개수 N과 컨베이어 벨트 위에 놓여져 있는 오렌지의 정보 Ai(1iN), 한 상자에 담을 수 있는 오렌지의 개수의 최대치 M, 상자를 포장하는 코스트 K가 주어져 있을 때, 상자 포장에 드는 비용 총합의 최솟값를 구하는 프로그램을 작성하라.

 

 ​ 




첫째 줄에 N, M, K가 공백을 사이에 두고 차례로 주어진다.

그 후 N개의 줄에 오렌지 크기가 주어진다. 
i(1≤i≤N)째 줄에 Ai가 주어진다.

모든 입력 데이터는 아래의 조건을 만족한다.

1≤N≤20,000
1≤M≤1,000
0≤K≤1,000,000,000
1≤Ai≤1,000,000,000 (1≤i≤N)
M≤N



N개의 오렌지를 포장하는 데 드는 최소 비용을 출력한다.

부분 문제
부분 문제 1 [39점]
N≤20

부분 문제 2 [30점]
N≤2,000
M≤100

부분 문제 3 [31점]
추가 제한 없음.


6 3 6
1
2
3
1
2
1
21


16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19
164


16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12
177


10 1 1000000000
1
1
1
1
1
1
1
1
1
1
10000000000






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.