1654번 - 이분 탐색 - 랜선 자르기

[ 풀이 ]

서로 다른 길이의 N개의 랜선을 잘랐을 때, 동일한 길이의 랜선이 K개 이상이어야 한다.
-> 동일한 길이의 랜선 개수 = x cm로 각 랜선을 나눴을 때의 몫의 합

 최대 랜선의 길이를 구하자
-> K를 만족하는 길이를 찾아도 우측 탐색을 지속함

랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.
-> 정수가 매우 큰 단위까지 사용된다.
-> long long 타입 사용

[ 코드 ]

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

using namespace std;

typedef long long ll;

int n = 10000;

vector<ll> lens;

int calcNumofLen(int length) { //동일한 길이의 랜선 개수 계산
	ll result = 0;
	for (auto l : lens) {
		result += l / length;
	}
	return result;
}

int main() {
	ll k;
	scanf("%d %d", &n, &k);

	ll length = 0;
	ll max_length = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &length);
		lens.push_back(length);
		if (length > max_length) {
			max_length = length;
		}
	}

	ll left = 1;
	ll right = max_length;
	ll result = max_length;

	while (left <= right) {
		ll mid = (left + right) / 2;
		ll count = calcNumofLen(mid);
		if (count < k) {
			right = mid - 1;
		}
		else { //조건 만족 시
			result = mid; //길이 저장
			left = mid + 1; //우측 탐색 지속
		}
	}

	printf("%d\n", result);

	return 0;
}