[BOJ 1654] 랜선 자르기

 

1654번: 랜선 자르기

K개의 랜선이 있는데, 이 K개의 랜선은 서로 다른 길이를 가지고 있으며,

서로 길이가 같은 N개의 랜선으로 분할한다는 문제입니다.

 

개인적으로 문제의 조건이 모호했다고 생각한 문제 중 하나입니다. 

K개의 랜선을 한 개도 빠짐없이 모두 사용해야 된다고 생각해서 약간 골머리가 났는데,

다 사용하지 않아도 되는거였습니다... 

즉, K-1개, K-2개.....의 랜선으로도 N개 이상을 만들 수 있다면 그또한 정답입니다. 

 

K는 1 ~ 10000이하의 정수, N은 100만이하의 수, 랜선의 길이는 1 ~ 2^31-1입니다.

 

4 11
802
743
457
539

길이 1부터 최댓값까지 모두 비교하여 '순차탐색'을 한다고 하면, 시간초과입니다. 

1 ~ 2^31-1의 수가 주어진다면, 2^31-1의 크기까지 돌아야하니까요.

 

최소 log의 시간으로 문제를 푸는것이 현명합니다.

역시 이분탐색으로 문제를 해결합니다.

 

이분탐색의 사용을 위해 주어진 랜선들의 '정렬'이 최우선 작업입니다.

주어진 랜선들을 정렬하면 457 539 743 802입니다.

 

그렇다면, 예시에서는 이분탐색의 left를 0으로 주고 right를 802(배열의 끝)로 주어

0과 802사이의 어떠한 숫자 mid가 n개 이상의 분할에 성공한다면 그 mid는 답의 후보가 될 것이고,

이러한 mid중 가장 큰 값을 return하면 됩니다.

 

이분탐색을 하는데 걸리는 시간은

log(랜선의 길이 = 2^31-1), 이를 K개에 대해 각각 시행해주어야하기 때문에

Klog(랜선의길이)로 무난하게 문제해결 가능합니다!

 

 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	int n, k;

	scanf("%d %d", &k, &n);

	vector<long long int> arr;
	long long int num;
	for (int i = 0; i < k; i++)
	{
		scanf("%lld", &num);
		arr.push_back(num);
	}
	
	sort(arr.begin(), arr.end());

	long long int ans = 0;
	long long int left = 0;
	long long int right = arr[k-1];

		while (left <= right)
		{
			long long int mid = (left + right + 1) / 2;
			int cnt = 0;
			for (int i = 0; i < k; i++)
			{
				cnt = cnt + (arr[i] / mid);
				if (cnt >= n)break;
			}

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

	printf("%lld\n", ans);
}