4 Problem A : 책 복사하기

Problem A : 책 복사하기

 

제한시간: 1000 ms    메모리제한: 32 MB

 

 

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

 

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

 

#include <stdio.h>
typedef long long LL;

#define MAX 10//510

int m, k, maxp;
LL book[510], sum[510];

void input()
{
	scanf("%d %d", &m, &k);
	maxp = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%lld", &book[i]);
		sum[i] = sum[i - 1] + book[i];
		if (maxp < book[i]) maxp = book[i];
	}
}

int chk(int p)
{
	int i, cnt = 1, end = 0;
	for (i = 1; i <= m; i++) {
		if (sum[i] - sum[end] > p) { // 연속된 숫자에서 구간 합을 계산 할 수 있음
			cnt++;
			end = i - 1; // 여기에 슬래쉬
			if (cnt > k) return 0; // 자른 것이 원하는 갯수보다 크면,
		}
	}
	return 1;
}

int b_search(int s, int e)
{
	if (s > e) return s; // return 조건 확인
	int m = (s + e) / 2; // 이 값으로 되는지 안되는지 넣어봄
	if (chk(m)) return b_search(s, m - 1); // 기준을 낮춤
	return b_search(m + 1, e);  // 기준을 높임
}
/*
int s = maxp, e = sum[m], m;
while (s <= e) {
m = (s + e) / 2;
if (chk(m)) e = m - 1;
else s = m + 1;
}
return s;
}
*/

void output(int p)
{
	int i, end = m, slash[510] = { 0 }, cnt = 1;
	for (i = m - 1; i > 0; i--) { // 슬래쉬가 들어가는 자리 입력함
		if (sum[end] - sum[i - 1] > p) {
			end = i;
			cnt++;
			slash[i] = 1; 
		}
	}
	for (i = 1; cnt < k && i <= m; i++) { // 아직 cnt가 차지 않았을 때
		if (slash[i] == 0) {
			slash[i] = 1;
			cnt++;
		}
	}
	for (i = 1; i <= m; i++) {
		printf("%lld ", book[i]);
		if (slash[i]) printf("/ ");
	}
	printf("\n");
}

int main()
{
	freopen("input.txt", "r", stdin);
	int T, ans;
	scanf("%d", &T);
	while (T--) {
		input();
		ans = b_search(maxp, sum[m]); // 이중 탐색으로 적절한 값 찾기
		output(ans);
	}
	return 0;
}