책 복사하기 1, 2(정올) / 백준 Copying books(3487) - 이분 탐색

책 복사하기1

https://www.acmicpc.net/problem/3487

3487번: Copying Books

https://zoosso.tistory.com/645

[Jungol] 정올 1156 책 복사하기2

https://howtoliveworldnice.tistory.com/429

백준 3487 Copying Books/정올 책 복사하기2 해결코드

페이지 수가 정해지면 몇 명의 서기공이 필요한지 알 수 있다.

가장 두꺼운 책의 페이지수부터 차례대로 필요한 서기공의 수를 계산 했을 때 그 수가 k명 이하가 나오면 그 수가 나누는 기준이 된다.

 

공략

1. 앞쪽 서기공이 적게 배정되어야 하니 뒤쪽부터 채워나가자.

2. 만약 맨앞에부터 1권도 배정이 안된 서기공이 있으면 맨 앞의 서기공부터 1권씩 배정한다.

 

 

#if 0
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

//ll book[511];
//ll N, K;
//
//int check(ll p)
//{
//	ll sum = 0, cnt = 1;
//	for (int i = 1; i <= N; i++)
//	{
//		sum += book[i];
//		if (sum > p)
//		{
//			if (++cnt > K) return 0;
//			sum = book[i];
//		}
//	}
//	return 1;
//}
//int b_search(int s, int e)
//{
//	if (s > e) return s;
//	ll m = (s + e) / 2;
//	if (check(m)) return b_search(s, m - 1);
//	return b_search(m + 1, e);
//}
//void output(int ans)
//{
//	ll i, sum = 0, cnt = 1, div[511] = { 0 };
//	for (int i = N; i > 0; i--)
//	{
//		sum += book[i];
//		if (sum > ans)
//		{
//			cnt++;
//			sum = book[i];
//			div[i] = 1;
//		}
//	}
//	for (int i = 1; cnt < K; i++)
//	{
//		if (div[i] == 0)
//		{
//			div[i] = 1;
//			cnt++;
//		}
//	}
//	for (int i = 1; i <= N; i++)
//	{
//		printf("%d ", book[i]);
//		if (div[i] == 1) printf("/ ");
//	}
//	printf("\n");
//}
//int main(void)
//{
//	freopen("input.txt", "r", stdin);
//	ll T, low, high, ans;
//	scanf("%d", &T);
//	while (T--)
//	{
//		low = high = 0;
//		scanf("%d %d", &N, &K);
//		for (int i = 1; i <= N; i++)
//		{
//			scanf("%d", &book[i]);
//			high += book[i];
//			if (low < book[i]) low = book[i];
//		}
//		ans = b_search(low, high);
//		output(ans);
//	}
//}

int TC;
int M;
int K;

bool check(int mid, vector<int> book)
{
	ll cnt = 1;
	ll sum = 0;
	for (int i = 1; i <= M; i++)
	{
		sum += book[i];
		if (sum > mid)
		{
			if(++cnt > K) return 0;
			sum = book[i];
		}
	}
	return (cnt <= K);
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	freopen("input.txt", "r", stdin);

	cin >> TC;
	while (TC--)
	{
		cin >> M >> K;
		
		ll tmp;
		ll low = 0;
		ll high = 0;
		ll ans = 0;
		vector<int> book;
		book.push_back(0);
		for (int i = 1; i <= M; i++)
		{
			cin >> tmp;
			book.push_back(tmp);
			if (tmp > low) low = tmp;
			high += tmp;
		}

		while (low <= high)
		{
			ll mid = (low + high) / 2;
			if (check(mid, book))
			{
				ans = mid;
				high = mid - 1;
			}
			else
				low = mid + 1;
		}

		ll sum = 0;
		ll cnt = 1;
		vector<int> div(510,0);
		for (int i = M; i > 0; i--)
		{
			sum += book[i];
			if (sum > ans)
			{
				cnt++;
				sum = book[i];
				div[i] = 1;
			}
		}
		for (int i = 1; cnt < K; i++)
		{
			if (div[i] == 0)
			{
				div[i] = 1;
				cnt++;
			}
		}
		for (int i = 1; i <= M; i++)
		{
			cout << book[i] << ' ';
			if (div[i] == 1) cout << "/ ";
		}
		cout << '\n';
	}
	return 0;

}
#endif

문제는 이렇게 해서 백준에 제출하면 절반만 성공한다. 뒤에 있는 건 틀렸다고 나온다;;

 

이유는 백준 문제는 "책 정리하기2" 유형으로 100,000권을 기준으로 잡아서 시간 오버가 나기 때문이다.

 

 

 

책 복사하기2

#if 1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int TC;
int M;
int K;
ll low = 0, high = 0, ans = 0;
vector<int> book(100010);

bool check(ll mid)
{
	ll cnt = 1;
	ll sum = 0;
	for (int i = 1; i <= M; i++)
	{
		sum += book[i];
		if (sum > mid)
		{
			if (++cnt > K) return 0;
			sum = book[i];
		}
	}
	return (cnt <= K);
}
void output(int idx, ll sum, int ck)
{
	if (idx < 1) return;
	if (sum + book[idx] > ans || idx <= ck)
	{
		output(idx - 1, book[idx], ck - 1);
		printf("%d / ", book[idx]);
	}
	else {
		output(idx - 1, sum + book[idx], ck);
		printf("%d ", book[idx]);
	}
		
}
int main(void)
{
	//freopen("input.txt", "r", stdin);

	scanf("%d %d", &M, &K);

	ans = 0;
	low = high = 0;
		
	for (int i = 1; i <= M; i++)
	{
		scanf("%d", &book[i]);
		if (book[i] > low) low = book[i];
		high += book[i];
	}

	while (low <= high)
	{
		ll mid = (low + high) / 2;
		if (check(mid))
		{
			ans = mid;
			high = mid - 1;
		}
		else
			low = mid + 1;
	}

	output(M, 0, K-1);

	return 0;

}
#endif