BOJ [14627] 파닭파닭

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

1. 분류

이분탐색

2. 풀이

시장에서 사 온 파의 일정량을 파닭에 넣고 남은 파는 라면에 넣어 먹으려고 한다.

주어진 조건은

1. 하나의 파닭에 한 개 이상의 파를 넣을 수 없고

2. 같은 양의 파를 넣어야 하며

3. 파닭에 넣을 파는 최대치가 되어야 한다는 것.

예제 입력은 다음과 같다.

3 5

440

350

230

파의 개수 3개, 주문받은 파닭의 개수 5개와 각 파의 길이가 입력으로 주어진다.

문제에 모호한 점이 있었다.

파는 1개 이상 넣을 수 없으니 파의 길이는 아무리 길어도 230을 넘을 수 없다라고 생각했었는데

그렇게 코드를 작성하니 0% 입구컷을 당해버렸다...

파닭에 같은 양의 파를 넣어야 하므로 이분 탐색의 초기 high값은 (파 길이의 합) / (파닭의 개수) 으로 주었다.

코드를 짤 때 주의할 점이 있는데, 예제 입력에 대한 답은 175가 되어야 하지만

174를 주어도 파닭의 개수 5개를 충족시킬 수 있다.

같은 개수의 파닭에 넣을 수 있는 양 중 최대치를 구할 수 있도록 고려하면 된다.

---

3. 소스코드

#include <cstdio>
typedef unsigned long long ull;
ull vegetable[1000000];

ull bs(int s, int c, ull sum)
{
	ull low = 1LL, high = sum / c, mid = (low + high) / 2LL;

	while (low <= high)
	{
		int cnt = 0;

		for (int i = 0; i < s; i++)
			cnt += vegetable[i] / mid;

		if (cnt >= c)
			low = mid + 1LL;
		else
			high = mid - 1LL;

		mid = (low + high) / 2LL;
	}
	
	return sum - mid * c;
}

int main()
{
	int s, c;
	ull sum = 0LL;
	scanf("%d %d", &s, &c);

	for (int i = 0; i < s; i++)
	{
		scanf("%llu", &vegetable[i]);
		sum += vegetable[i];
	}

	printf("%llu\n", bs(s, c, sum));

	return 0;
}