외양간 > 문제은행



알고리즘 그리디

1816 : 외양간

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 134 회    시도횟수: 474 회   



폭풍우 치는 어느 날 밤에 소들이 있는 외양간의 지붕과 문이 날아가 버렸다. 

그러나 다행이도, 많은 소들이 외양간에서 대피하였다.

 

소들은 긴 줄로 나란히 서서 외양간에서 밤을 보냈다. 

어떤 외양간은 소들이 없었다. 모든 외양간은 똑같은 넓이로 되어있다.

 

농부 창호는 가능한 빨리 외양간 앞쪽에 판자를 세워야 한다. 문이 날아갔기 때문이다. 

판자 공급자는 창호가 원하는 크기대로 판자를 공급한다. 그러나 공급자가 공급하는 판자의 수는 정해져있다. 

창호는 구입해야 하는 판자의 총길이를 최소화하기를 원한다.

 

M(1≤M≤50)은 판자 공급자에게서 구입할 수 있는 최대 판자수이다. S(1≤S≤200)은 총 외양간의 수이다. 

C(1≤C≤S)는 소가 들어 있는 외양간의 수이다. 그리고 다음 줄부터 C개의 줄까지는 소가 들어 있는 외양간의 번호이다.

 

소가 들어있는 모든 외양간의 문을 M개의 판자로 막을 때 판자의 총 길이를 최소화하는 길이가 얼마인지 계산하여라.




첫 줄에는 세 개의 수가 나오는데, 이 수가 M, S, C이다. 두 번째 줄부터 C개의 줄까지는 소가 들어 있는 외양간의 번호이다.




M개의 판자로 소가 들어 있는 외양간을 막을 때, 판자의 총 길이를 출력한다.



4 50 18 
3 
4 
6 
8 
14 
15 
16 
17 
21 
25 
26 
27 
30 
31 
40 
41 
42 
43
25


입력에서 판자 4개를 사용하여야 하므로, 3~8, 14~17, 21~31, 40~43으로 4개의 판자로 나누면, 물론 1개의 판자의 길이는 다를 수 있지만, 사용한 4개의 판자의 총길이는 25로 여러 가지 경우 중에서 가장 짧다.




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