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

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

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

당시 극장에서는 유명한 비극을 상연하는 중이었는데,

여러 권으로 나뉜 대본을 배우들에게 주기 위해 서기공들을 고용했다.

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

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

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

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

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

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

책 복사하기2 timer 1초 memory 32MB

책 복사하기2 1초 32MB