Informatica Online Judge

  나쁜 녀석, 승한 [2123 / 084B]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 6   Total Tried : 7


The Champion of this Problem (C++) : gs16106 - 206ms / 1095byte
My Best Submission (C++) : N/A

[koistudy.net (34th 백윤기)]

Background

승한이는 친구들에게 “나쁜 녀석” 이라고 놀림을 많이 받는다. 이에 스트레스를 받은 승한이는 자신을 놀린 친구들에게 “장문의 카톡”을 보내 놀리지 말아달라고 할 예정이다.

N명의 친구들에게 모두 카톡을 한 통씩 보내기에는 돈이 부족하기 때문에 최대 M개의 카톡밖에 보내지 못한다. 따라서 승한이는 친구들을 M개의 그룹으로 나누어 카톡을 보낸다.

각 친구들과 승한이 사이의 친밀도가 A[i]로 주어졌을 때, 승한이는 카톡을 보내는 “어색함”을 최소로 하고자 한다.

그룹 A의 “어색함”은, (그룹 A의 사람수 – 1) * (그룹 A 의 사람들의 친밀도의 합) 이다.
M개의 그룹들의 “어색함”의 총합을 최소로 하도록 승한이를 도와 N 명의 사람들을 적절히 그룹 짓자.

( 예제는 채점 데이터와 무관하다. )

Input

첫 줄에 N, M 이 입력된다. ( 2 <= M <= N <= 5000 )
2번째 줄부터 N+1 번째 줄까지 각 사람의 친밀도를 나타내는 정수가 주어진다. (10000 이하)

Output

최소 “어색함”을 출력한다.

IO Example

5 2
1
2
3
4
5

출력 예제
21

설명 : (1, 2, 3) (4, 5) 로 묶으면 6 * 2 + 9 * 1 = 21 이 최소다.

입력 예제 2
5 2
1
2
3
4
1000

출력 예제
30

설명 : (1, 2, 3, 4) (5) 로 묶으면 10 * 3 = 30 이 최소다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]