문제
모든 사람들은 공평한 것을 좋아하고 불공평한 것을 싫어한다(당연한 것이지만 말이다).
이 현상은 특히 정올학교에서 알고리즘을 공부하는 학생들에게 심하게 나타나서, 요즘 이쌤께서 아주 고민이 많으시다.
상황은 다음과 같다.
정올학교를 후원하는 베이커리 체인점인 빨리바게뜨 에서는 다양한 종류의 빵을 학교로 보내준다.
그런데 빨리바게뜨 빵은 사실 각 빵마다 맛이 제각각이어서,
학생들에게 하나씩 나누어 주다 보면 누구는 맛있는 빵을 받아서 좋고,
누구는 아니어서 학생들끼리 불만이 생길 수 밖에 없다.
이 때의 학생들의 분노하는 정도는 “모든 빵 맛 차이의 합”으로 계산한다.
예를 들면 다음과 같다.
3명의 학생들에게 맛 3, 4, 4짜리 빵을 각각 주었을 때의
|1번빵-2번빵|+|1번빵-3번빵|+|2번빵-3번빵|=|3-4|+|3-4|+|4-4| = 2가 총 분노도가 된다.
( |x|는 절대값 x를 뜻하며, 이는 부호를 뗀 수를 말한다. 즉 |2|는 2이고, |-3|=3이다.)
오늘도 빨리바게뜨에서 n개의 빵을 보내주었다. 오늘 출석한 학생은 k명이다.
분노도가 높을수록 학생들이 얼굴을 많이 찌푸리고, 이쌤이 많이 피곤해하신다.
최소 분노도를 출력하는 프로그램을 작성하라.
입력
첫 줄에 오늘 온 빵의 개수 n이 주어진다.(
둘째 줄에 학생의 수 k가 주어진다(
다음 줄부터 n개의 줄에 걸쳐 각 빵의 맛( 10억 이하의 0 이상의 정수)이 정수로 주어진다.
출력
k개의 빵을 선택해서 나누어 주었을 때 얻을 수 있는 최소 분노도를 출력하라.
예제 #1
7
3
10
100
300
200
1000
20
30
40
예제 #2
10
4
1
2
3
4
10
20
30
40
100
200
10
로그인해야 코드를 작성할 수 있어요.