백준 1654 - 랜선 자르기

주어진 랜선 K개를 잘라 N개의 동일한 길이를 랜선을 만들 때 가장 긴 랜선을 찾는 문제입니다.

단순하게 랜선 K개를 모두 돌면서 1부터 N까지 잘라보며 가장 긴 길이의 랜선을 찾아볼 수도 있지만, Time complexity가 $O(N^2)$이고 최대 10억번 반복되기에 시간 초과가 발생합니다.

Binary Search를 통해 Time complexity를 $O(N\log N)$ 까지 줄일 수 있습니다.

어차피 결과 랜선의 길이는 1에서 가장 긴 랜선의 길이 사이 값이므로 해당 범위를 binary search를 통해 탐색하며 가장 긴 랜선을 찾습니다.

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

int main()
{
	int K, N;
	std::cin >> K >> N;

	std::vector<long long> lines;

	for (int i = 0; i < K; i++)
	{
		long long temp;
		std::cin >> temp;
		lines.push_back(temp);
	}

	std::sort(lines.begin(), lines.end(), [](const long long a, const long long b) {return a > b; });

	long long length = 0;

	long long left = 1;
	long long right = lines[0];
	long long mid = (left + right) / 2;

	long long result = 0;

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

		int tempCnt = 0;
		for (int i = 0; i < K; i++)
			tempCnt += lines[i] / mid;

		if (tempCnt < N)
			right = mid - 1;
		else
		{
			left = mid + 1;
			result = mid;
		}
	}

	std::cout << result;


	return 0;
}