[백준/C++] 1654 랜선자르기

1654 랜선자르기

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int k, n;
	cin >> k >> n;
	vector<unsigned int> arr(k);
	unsigned int right = 0, left = 1, mid, ans = 0;
	for (int i = 0; i < k; ++i)
	{
		unsigned int tmp;
		cin >> tmp;
		arr[i] = tmp;
		right = max(right, tmp);
	}

	while (left <= right)
	{
		unsigned int check = 0;
		mid = (right + left) / 2;
		for (int i = 0; i < k; ++i)
			check += arr[i] / mid;
		if (check >= n)
		{
			left = mid + 1;
			ans = max(mid, ans);
		}
		else
			right = mid - 1;
	}
	cout << ans;

	return 0;
}

• 이분 탐색을 사용해야 하는 문제
• 주어진 랜선중 가장 긴 크기가 right가 된다.
• 정답이 나와도 최대가 아닐 수 있기 때문에 최대를 구해야 한다.