COCI 2014/2015 contest2 3- 훈련 계획(STUDENTSKO) > 문제은행 : 정보올림피아드&알고리즘




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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP