2887 : 훈련 계획(STUDENTSKO)
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 28 회
- 시도횟수
- 55 회
문제
세계 볼링 선수권 대회에 참여하고자 하는 정올국에서는 볼링선수들의 훈련 계획을 세웠다.
N명의 선수들의 실력을 수치화 하여 실력이 낮은 사람 K명을 첫 팀으로
다음으로 실력이 낮은 사람 K명을 두 번째 팀으로 등등... N / K팀으로 나누어 훈련시킬 계획이다.
훈련 첫날 전국의 N명의 선수들이 훈련장으로 모여 선수등록을 하려고 줄을 섰다.
선수 등록 담당 형돈이는 선수들이 실력이 낮은 팀부터 높은 팀 순으로 차례로 등록하기를 바란다.
이를 위하여 형돈이는 어떤 위치의 선수 한명을 뽑아 임의의 위치에 재배치하는데 이 때 1분이 소요된다고 한다.
또한 이러한 재배치를 원하는 만큼 할 수 있다고 한다.
전체 선수의 수와 한 팀에 속해야 하는 선수의 수 그리고 각 선수의 실력이 주어질 때 형돈이를 도와 선수들을 줄 세우는데 필요한 시간을 최소화 해보자.
입력형식
첫 행에 등록 선수의 인원수를 나타내는 N ( 1 ≤ N ≤ 5000)과 각 팀의 구성 인원수 K( N의 약수)가 공백으로 구분되어 입력된다.
다음 행에 N명의 선수들에 대한 실력 Vi ( 1 ≤ Vi ≤ 109) 가 공백으로 구분하여 입력된다.
출력형식
선수들이 실력이 낮은 팀부터 높은 팀 순으로 차례로 재배치하여 줄 세우는데 필요한 최소 시간을 출력한다.
입력 예4 1 9 12 5 13 |
출력 예1 |
입력 예6 2 16 2 1 7 5 10 |
출력 예1 |
입력 예6 3 7 9 8 3 6 5 |
출력 예3 |