백준 3487: Copying Books

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

 

핵심 아이디어

 이 문제는 평소와 달리 핵심 아이디어는 금방 떠올렸지만, 구현과 너무 씨름을 해서 시간을 소비하게 된 문제였다.

 

일단 매개 변수 탐색 내지 이분 탐색을 사용하는 것은 금방 알아챘다.

scriber에게 할당할 books의 최대 양을 최소화 하려면, books의 양을 이분 탐색해서, 해당 양이 K명 내에서 해결할 수 있는지 확인만하면 된다.

bool solve(ll l)
{
	ll s = 0;
	int cnt = 1;
	for (int i = M - 1; i >= 0; i--)
	{
		s += P[i];
		if (s > l)
		{
			s = P[i];
			++cnt;
		}
	}
	return cnt <= K;
}

////

ll l = 0, r = 1e18;
for (int i = 0; i < M; i++)
{
	cin >> P[i];
	l = max(l, P[i]);
	S += P[i];
}
l--;
while (l + 1 < r)
{
	ll m = (l + r) / 2;
	if (solve(m)) r = m;
	else l = m;
}

문제는 출력이다. 단순하게 이렇게 계산하면, 답은 여러개지만, 이 문제에선 첫 scriber에게 최소한의 books를 할당하도록하는 단 하나의 답을 원하고 있다. 그리디적인 발상이 필요한 것은 알겠지만, 이것을 어떻게 계산할지가 문제였다.

 

방황

먼저 떠올린 아이디어는 다음과 같다.

for문을 돌며 배열을 순회하는데, 남은 할당자와 최대 할당량으로 현재의 count에서 끊을 수 있는지 확인하는 방식이였다.

ll s = 0;
int rem = K - 1;
for (int i = 0; i < M; i++)
{
	s += P[i];
	cout << P[i] << " ";
	if (r * rem >= S - s)
	{
		if (i != M - 1) cout << "/ ";
		S -= s;
		rem--;
		s = 0;
	}
}
cout << '\n';

다소 어영부영한 아이디어였기에, 결국 틀렸지만..

여러 조정을 했지만, 결국 해결할 수 없었기에, 다른 아이디어를 시험해보기로 했다.

사실 이 아이디어가 먼저 떠올렸지만, 구현에 애먹을것 같아서, 위의 아이디어부터 시험했었다.

 

뒤에서 부터 for문을 돌며, 합을 구한뒤, 그것이 이분 탐색으로 구한 값을 넘으면, 끊는 방식이다.

결론부터 말하자면, 이 아이디어가 맞다. 그런데, 생각 이상으로 구현이 까다로워서 많이 애먹었다.

예를 들어서, 중간에, scriber와 books의 값이 같아지면, 나머지 scriber에 각각 하나씩의 books를 할당하는 것은

반례를 일일히 들어서야 구현해야한다는 것을 깨달았다.

 

그렇게 나온 코드는 지금보면 이해하기가 힘들다.

		ll s = 0;
		int cnt = 0, rem = K;
		vector<int> c;
		for (int i = M - 1; i >= 0; i--)
		{
			s += P[i];
			if (s > r)
			{
				s = P[i];
				c.push_back(cnt);
				rem--;
				if (rem == i + 1)
				{
					for (int j = 0; j < rem; j++)
						c.push_back(1);
					break;
				}
				cnt = 1;

			}
			else
			{
				++cnt;
			}
		}
		if(rem == 1) c.push_back(cnt);
		reverse(c.begin(), c.end());
		int idx = 0;
		for (int i = 0; i < c.size(); i++)
		{
			for (int j = 0; j < c[i]; j++, idx++)
				cout << P[idx] << " ";
			if(i < c.size() -1 )
				cout << "/ ";
		}
        
///

		ll s = 0;
		int cnt = 0, rem = K;
		vector<int> c;
		bool f = true;
		for (int i = M - 1; i >= 0; i--)
		{
			s += P[i];
			if (s > r)
			{
				s = P[i];
				c.push_back(cnt);
				rem--;
				if (rem == i + 1)
				{
					f = false;
					for (int j = 0; j < rem; j++)
						c.push_back(1);
					break;
				}
				cnt = 1;

			}
			else
			{
				++cnt;
			}
		}
		if (f)
		{
			c.push_back(cnt - rem + 1);
			for (int j = 0; j < rem - 1; j++)
				c.push_back(1);
		}
		reverse(c.begin(), c.end());
		int idx = 0;
		for (int i = 0; i < c.size(); i++)
		{
			for (int j = 0; j < c[i]; j++, idx++)
				cout << P[idx] << " ";
			if(i < c.size() -1 )
				cout << "/ ";
		}
		cout << '\n';

해결

어찌저치 시행착오를 거쳐서

		ll s = 0, cnt = 0;
		int rem = K;
		vector<int> c;
		for (int i = M - 1; i >= 0; i--)
		{
			++cnt;
			s += P[i];
			if (s > r)
			{
				c.push_back(cnt - 1);
				s = P[i];
				cnt = 1;
				--rem;
			}
			if (i + 1 == rem)
			{
				c.push_back(cnt);
				while (i-- > 0) c.push_back(1);
				cnt = -1;
				break;
			}
			
		}
		if (cnt > 0) c.push_back(cnt);
		reverse(c.begin(), c.end());
		int idx = 0;
		for (int i = 0; i < c.size(); i++)
		{
			for (int j = 0; j < c[i]; j++, idx++)
				cout << P[idx] << " ";
			if (i < c.size() - 1)
				cout << "/ ";
		}
		cout << '\n';

더 깔끔하게 코드를 구성하게 되었다.

전체코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
int N, M, K;
ll P[501];
bool solve(ll l)
{
	ll s = 0;
	int cnt = 1;
	for (int i = M - 1; i >= 0; i--)
	{
		s += P[i];
		if (s > l)
		{
			s = P[i];
			++cnt;
		}
	}
	return cnt <= K;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	while (N--)
	{
		ll S = 0;
		cin >> M >> K;
		ll l = 0, r = 1e18;
		for (int i = 0; i < M; i++)
		{
			cin >> P[i];
			l = max(l, P[i]);
			S += P[i];
		}
		l--;
		while (l + 1 < r)
		{
			ll m = (l + r) / 2;
			if (solve(m)) r = m;
			else l = m;
		}
		ll s = 0, cnt = 0;
		int rem = K;
		vector<int> c;
		for (int i = M - 1; i >= 0; i--)
		{
			++cnt;
			s += P[i];
			if (s > r)
			{
				c.push_back(cnt - 1);
				s = P[i];
				cnt = 1;
				--rem;
			}
			if (i + 1 == rem)
			{
				c.push_back(cnt);
				while (i-- > 0) c.push_back(1);
				cnt = -1;
				break;
			}
			
		}
		if (cnt > 0) c.push_back(cnt);
		reverse(c.begin(), c.end());
		int idx = 0;
		for (int i = 0; i < c.size(); i++)
		{
			for (int j = 0; j < c[i]; j++, idx++)
				cout << P[idx] << " ";
			if (i < c.size() - 1)
				cout << "/ ";
		}
		cout << '\n';
	}
}

생구현 문제가 아닌 문제로 이렇게 구현이 힘들었던것은 오랜만이다.