BOJ 1654 랜선 자르기

이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개(이상)의 랜선을 만들수 있는지 없는지에 초점을 두었다. 여기서 핵심은 적절한 랜선의 길이를 어떻게 잡는가 이다. 

 

여기서 선택지는 두가지로 다음과 같다.

1. 가장 큰 길이를 기준으로 적절한 랜선 길이를 찾아내기

2. 가장 작은 길이를 기준으로 적절한 랜선 길이를 찾아내기

 

가장 작은 길이로 적절한 랜선 길이를 찾아낼 경우 최대 랜선의 길이를 구할 수  없다. 

예를들어 입력이 

2 10

100

4

일때 최대 랜선의 길이는 10 이 되지만 가장 작은 길이를 기준으로 하였을 경우 결과는 4가 된다.

 

가장 큰 길이의 랜선을 기준으로 적절한 랜선 길이를 찾아보자!!

 

랜선의 길이를 순차적으로 줄여나가며 각 경우에 대해 N개의 랜선을 만들수 있는지 없는지 확인하는 것은 랜선의 길이가 최대 1,000,000 이기 때문에 O(K*N) = 10,000,000,000 으로 시간초과가 발생한다. 

 

이를 해결하기 위해 이분 탐색을 이용하여 적절한 랜선 길이를 구해 문제를 해결한다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

long long k, n;
vector<long long> len;
long long result;

bool cmp(long long a, long long b)
{
	return a > b;
}

long long cut(long long length)
{
	if(length == 0)
	{
		return 0;
	}

	long long cutCnt = 0;
	for(auto l : len)
	{
		cutCnt += l / length;
	}
	return cutCnt;
}

void BS(long long l, long long r)
{
	if(l > r)
	{
		return;
	}

	long long mid = ceil((double)(l + r) / 2);

	long long cnt = cut(mid);

	if(cnt < n)
	{
		BS(l, mid-1);
	}
	else
	{
		result = max(result, mid);
		BS(mid+1, r);
	}
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> k >> n;

	for(int i = 0; i < k; i++)
	{
		long long num;
		cin >> num;
		len.push_back(num);
	}

	sort(len.begin(), len.end(), cmp);

	BS(0, len[0]);
	cout << result;
}