COCI 2014/2015 contest1 5- 소음 줄이기(ZABAVA) > 문제은행 : 정보올림피아드&알고리즘




2870 : 소음 줄이기(ZABAVA)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
11 회   
시도횟수
37 회   

문제

새로운 학생 기숙사가 완공되었다. 기숙사는 M개의 건물로 구성되어 있고 1 ~ M까지 번호가 매겨져 있다. 기숙사는 초기에는 비어있지만 N명의 학생들이 하루에 한 명씩 입주한다. 새로운 학생이 한 건물에 입주할 때마다 그 건물에서는 파티가 열린다. 파티가 열릴 때는 소음이 발생하는데 소음의 크기레벨은 그 건물에 있는 학생 수와 같다.

 

기숙사 관리인 기찬이는 유난히 소음을 싫어한다. 그래서 새로운 학생이 기숙사에 입사 할 때는 파티의 소음이 적정수준을 유지하도록 때때로 어느 한 건물을 모두 비워놓는다고 한다. 어떤 건물을 비울 때는  완전히 다른 곳으로 현재 건물의 모든 학생들을 이주시킨다고 한다. 기찬이는 원하는 날에 어느 건물이든 비울 수 있다. 그런데 이러한 건물을 비우는 일은 많은 비용을 발생시키므로 많아야 K번만 할 수 있다고 한다.

 

기숙사 입주 정보가 주어질 때 입사하는 동안 발생하는 소음 레벨의 총합을 최소화하도록 하는 프로그램을 작성하여 관리인 기찬이를 도와주자.


입력형식

첫 행에 학생 수 N(1 ≤ N ≤ 1,000,000), 기숙사 건물 수 M( 1 ≤ M ≤ 100), 건물을 비울 수 있는 횟수 K (1 ≤ K ≤ 500) 이 공백을 기준으로 입력된다. 이 후 N개의 행에 Si가 입력되는데 i번째 날에 한 학생이 Si번 건물로 입주하는 정보이다.

출력형식

입사하는 동안 발생하는 소음레벨의 총합을 최소로 할 때 그 총합을 하나의 행에 출력한다. <입력 예1 에 대한 설명> 총합이 7이 되는 한 예는 첫 번째, 세 번째 입사 후에 건물을 비운다. 이렇게 하면 소음 레벨은 각각 1, 1, 2, 1, 2가 된다. 건물을 비우지 않는 경우 소음 레벨은 각각 1, 2, 3, 4, 5가 된다. <입력 예2 에 대한 설명> 총합이 18이 되게 하는 한 가지 방법은 1번 건물은 네 번째, 여덟 번째 날에 비우고, 2번 건물은 여섯 번째 날에 비우면 된다. 이렇게 하면 소음 레벨은 각각 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2가 된다.

입력 예

5 1 2
1
1
1
1
1

출력 예

7

입력 예

11 2 3
1
2
1
2
1
2
1
2
1
2
1

출력 예

18


경기도 안양시 동안구 평촌대로 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