시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 262 | 73 | 53 | 29.282% |
오늘은 기쁜 날이다. 개미와 코끼리의 결혼식 날이기 때문이다. 결혼 축하 의식으로 기차놀이를 하기로 했다. 기차놀이란 뒷사람이 앞사람의 어깨에 손을 얹고 한 줄로 마을을 돌아다니는 것이다. 그런데 앞사람과 뒷사람의 키 차이가 많이 나면 기차가 아름다워 보이지 않는다. 아름다움을 중요시 여기는 “앙두레 강”은 기차가 아름답게 보이도록 기차에서 사람들의 순서를 잘 조정하기로 했다.
인접한 앞뒤사람의 키 차이를 모두 더한 것이 최소가 될 때 기차는 가장 아름답게 보인다.
하지만 한 가지 문제가 있다. 결혼식에 사자가족도 참석했는데 사자가족은 서열이 엄격해서 서열이 낮은 사자가 서열이 높은 사자보다 기차에서 앞쪽에 위치하면 안 된다. 이 조건만 만족한다면 결혼식에 참석한 사람들의 순서를 마음대로 바꾸어도 된다.
“앙두레 강”을 도와 결혼 축하 기차를 아름답게 만들어 보도록 하자.
첫 줄에 N(1 ≤ N ≤ 10000)과 K(1 ≤ K ≤ N, K ≤ 1000)가 입력된다. N은 결혼식에 참가한 사람의 수이고 K는 결혼식에 참가한 사자가족의 수이다. 바로 이어서 (우선순위가 높은 사자부터) 사자가족의 키가 K줄에 걸쳐 입력된다. 그리고 그 다음 줄부터 (N-K)줄에 다른 사람들의 키가 입력된다. 키는 231-1보다 작거나 같은 자연수이다.
기차에서 인접한 앞뒤사람의 키 차이를 모두 더한 값을 출력하시오. 답은 231-1를 넘지 않는다.
5 3 1900 1300 1500 1200 1600
1000
3 2 2000 1200 1500
800
6 3 1700 1900 1500 1800 1750 1300
800