버블 버킷 정렬
면접 대비시간 제한1초메모리 제한512 MB
n개의 거품 크기를 최대 b개의 버킷으로 나누어, 각 버킷에서 가장 큰 값과 가장 작은 값의 차이를 제곱해 더한 값이 최소가 되도록 한다.
문제
Belinda는 거품을 부는 것을 좋아한다. 하루 종일 거품을 불고 나서, Belinda는 거품을 양동이에 담아 겨울 동안 보관하면 좋겠다고 생각한다.
각 거품은 양동이 하나에 넣어야 하며, 각 양동이에 담긴 거품들의 크기는 가능한 한 비슷하면 좋다. 양동이의 점수는 그 양동이에서 가장 큰 거품과 가장 작은 거품의 크기 차이를 제곱한 값이다. Belinda는 각 양동이에 원하는 만큼 거품을 넣을 수 있다. 양동이가 비어 있다면 그 점수는 0이다.
예를 들어 양동이에 다음과 같이 담겼다면: [1, 2, 3], [3, 5], [4, 4], 총 점수는 (3 − 1)2 + (5 − 3)2 + (4 − 4)2 = 8이다. 거품의 크기들이 주어졌을 때, Belinda가 얻을 수 있는 최소 총 점수는 얼마인가?
입력
첫째 줄에는 거품의 개수 n (1 ≤ n ≤ 200)과 양동이의 개수 b (1 ≤ b ≤ 200)가 주어진다.
다음 n개의 줄은 거품을 나타낸다. 각 줄에는 하나의 정수 k (1 ≤ k ≤ 109)가 주어지며, 이는 해당 거품의 크기이다.
출력
Belinda가 얻을 수 있는 최소 총 점수를 출력한다.