BOJ [1654] 랜선 자르기

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

1. 분류

이분탐색

2. 풀이

14627번 파닭파닭과 굉장히 유사한 문제이다(http://private-space.tistory.com/11).

파닭파닭 문제에서 조금 변형하여 해결했다.

---

3. 소스코드

#include <cstdio>
typedef unsigned long long ull;
ull wire[10000];

ull bs(int k, int n, ull max)
{
	ull low = 1, high = max, mid = (low + high) / 2;

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

		for (int i = 0; i < k; i++)
			cnt += wire[i] / mid;

		if (cnt >= n)
			low = mid + 1;
		else
			high = mid - 1;
			
		mid = (low + high) / 2;
	}

	return mid;
}

int main()
{
	int k, n; 
	ull max = 0;
	scanf("%d %d", &k, &n);
	for (int i = 0; i < k; i++)
	{
		scanf("%llu", &wire[i]);
		max = max < wire[i] ? wire[i] : max;
	}

	printf("%llu\n", bs(k, n, max));
	
	return 0;
}