책 복사하기 > 문제은행

본문 바로가기


알고리즘 자료구조1

1137 : 책 복사하기

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 148 회    시도횟수: 922 회   



윤전기의 발명 전에는 책의 사본을 만드는 것이 무척 고통스러운 일이었다. 당시에는 책을 베껴쓰는 사람들 (서기공)이 전문으로 책을 베껴쓰곤 했다. 이 작업은 몹시 지루했는데, 작업을 일찍 끝낼 유일한 방법은 더 많은 서기공을 고용하는 것 뿐이었다.

 

당시 극장에서는 유명한 비극을 상연하는 중이었는데, 여러 권으로 나뉜 대본을 배우들에게 주기 위해 서기공들을 고용했다. 대본은 m권으로 나뉘어 있으며, 서기공의 수는 k이다. (k <= m) 이 때, 각 서기공마다 한 권 이상씩의 대본을 배정해서 책을 베껴쓰게 하려고 한다.

 

각 서기공은 연속된 권을 베껴써야 한다. (예를 들어, 1 2 3 권이나 3권을 할 수는 있지만, 1 2 4 나 3 5 권을 베껴쓸 수는 없다. 한 권을 두 사람이 나누어서 베낄 수 없다. 이 때, 모든 대본이 다 완성되는 시간은 가장 많은 페이지를 베껴써야 하는 서기공의 업무량에 달렸다.


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


첫 줄에 테스트 케이스의 개수가 들어온다. 각 테스트 케이스의 첫째 줄에는 책의 권수 m과 서기공의 수 k (각각 500 이하, k <= m) 가 주어진다. 그 후 m개의 (1억 이하의 자연수) 각 책의 페이지 수가 주어진다.



각 테스트 케이스마다, 책들을 k개의 구간으로 쪼개서 출력한다. 예제 출력을 참조한다. 만약 답이 두 개 이상 있다면, 첫 번째 서기공이 할 일이 가장 작은 답을 출력한다. 그래도 두 개 이상 있다면, 두 번째 서기공이 할 일이 가장 작은 답을 출력하며, 그래도 두 개 이상 있을 경우 이런 식으로 반복한다.


[Copy]
2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
[Copy]
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100




Central Europe 1998 Copying Books, poj 1505

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.