4 Problem A : 책 복사하기

책의 권수 m과 서기공의 수 k가 주어진다

가장 많은 페이지를 맡은 서기공의 페이지 수를 최소화할 수 있도록,

책들을 k명의 서기공에게 배분하는 프로그램을 작성하라

 

가능한 범위를 선정하고, 그에 따라 배분한 후 출력

#include <stdio.h>

#define MAX 510 // 책이 들어오는 수 

typedef long long LL; // 책, 책 누적값

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

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; // cnt 가 
		}
	}
	return 1;
}

int b_search()
{
	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; // 이것이 범위 선정임 예제를 기준으로 1700으로 하면 100~500 포함 가능 600~700포함 가능/ 800~700 포함 가능
}

void output(int p)
{
	int i, end = m, slash[MAX] = { 0 }, cnt = 1;
	
	// 구한 P를 기준으로 slash를 나눔
	for (i = m - 1; i > 0; i--) {
		if (sum[end] - sum[i - 1] > p) {
			end = i;
			cnt++;
			slash[i] = 1;
		}
	}

	// slash가 부족할 때
	for (i = 1; cnt < k && i <= m; i++) {
		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()
{
	int T, ans;
	scanf("%d", &T);
	while (T--) {
		input();
		ans = b_search();
		output(ans);
	}
	return 0;
}

 

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