[210617][백준/BOJ] 1654번 랜선 자르기

문제

입출력

풀이

백준 2805 나무 자르기랑 비슷한 문제이며 이분 탐색으로 풀 수 있다.

정확히 n개의 랜선을 찾는것이 아니라 n개 이상의 랜선을 찾는 문제이다.
1. left를 0이 아닌 1로 초기화 해야한다.
2. int형 범위를 벗어남으로 long long형으로 선언해야한다.

코드

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll k, n, maxH = 0;
	cin >> k >> n;
	vector<ll> V(k);

	for (int i = 0; i < k; ++i)
	{
		cin >> V[i];
		maxH = max(maxH, V[i]);
	}

	ll left = 1, right = maxH, ans = 0;

	while (left <= right)
	{
		ll mid = (left + right) / 2;
		ll sum = 0;

		for (int i = 0; i < k; ++i)
			sum += (V[i] / mid);

		if (sum >= n)
		{
			ans = max(ans, mid);
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	cout << ans << '\n';
}