Central Europe 1998, poj 1505- 책 복사하기 > 문제은행 : 정보올림피아드&알고리즘



1137 : 책 복사하기

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
264 회   
시도횟수
1380 회   

문제

윤전기의 발명 전에는 책의 사본을 만드는 것이 무척 고통스러운 일이었다. 

당시에는 책을 베껴쓰는 사람들 (서기공)이 전문으로 책을 베껴쓰곤 했다. 

이 작업은 몹시 지루했는데, 작업을 일찍 끝낼 유일한 방법은 더 많은 서기공을 고용하는 것 뿐이었다.

 

당시 극장에서는 유명한 비극을 상연하는 중이었는데, 여러 권으로 나뉜 대본을 배우들에게 주기 위해 서기공들을 고용했다. 

대본은 m권으로 나뉘어 있으며, 서기공의 수는 k이다. (k <= m) 

이 때, 각 서기공마다 한 권 이상씩의 대본을 배정해서 책을 베껴쓰게 하려고 한다.

 

각 서기공은 연속된 권을 베껴써야 한다. (예를 들어, 1 2 3 권이나 3권을 할 수는 있지만, 1 2 4 나 3 5 권을 베껴쓸 수는 없다. 

한 권을 두 사람이 나누어서 베낄 수 없다. 

이 때, 모든 대본이 다 완성되는 시간은 가장 많은 페이지를 베껴써야 하는 서기공의 업무량에 달렸다.


가장 많은 페이지를 맡은 서기공의 페이지 수를 최소화할 수 있도록 책들을 k명의 서기공에게 배분하는 프로그램을 작성하라.


입력형식

첫 줄에 테스트 케이스의 개수가 들어온다. 

각 테스트 케이스의 첫째 줄에는 책의 권수 m과 서기공의 수 k (각각 500 이하, k <= m) 가 주어진다. 

그 후 m개의 (1억 이하의 자연수) 각 책의 페이지 수가 주어진다.


출력형식

각 테스트 케이스마다, 책들을 k개의 구간으로 쪼개서 출력한다. 

예제 출력을 참조한다. 

만약 답이 두 개 이상 있다면, 첫 번째 서기공이 할 일이 가장 작은 답을 출력한다. 

그래도 두 개 이상 있다면, 두 번째 서기공이 할 일이 가장 작은 답을 출력하며, 

그래도 두 개 이상 있을 경우 이런 식으로 반복한다.


입력 예

2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100

출력 예

100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100


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

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

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP