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

문제링크

---

설명

index를 기준으로 하는 것이 아닌 value를 기준으로 이분탐색을 진행한다.
가장 큰 수를 찾고 mid를 구한다음, 각 랜선들을 mid로 자르고 잘린 개수를 세어 mid의 길이를 늘려서 크게크게 잘라 랜선의 개수를 줄일지, 줄일지를 결정한다.

그러니까 만약 목표치보다 너무 많이 잘랐다 싶으면 left = mid + 1을 해서 mid의 값을 크게 잡아주고, 목표치보다 작게 잘랐다 싶으면 mid의 값을 작게해서 잘게 잘라준다.

---

제출코드

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

using namespace std;

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

	int k, n;
	int max = 0;

	cin >> k >> n;
	vector<int> v(k);

	for (int i = 0; i < k; i++)
	{
		cin >> v[i];
		if (max < v[i])
			max = v[i];
	}

	long long left = 1; // 자연수
	long long right = max;

	while (left <= right)
	{
		long long mid = (left + right) / 2;
		int cnt = 0;
		
		for (int i = 0; i < k; i++)
			cnt += v[i] / mid;

		if (cnt >= n)
			left = mid + 1;
		else
			right = mid - 1;
	}

	cout << left-1;

	return 0;
}