[C++] 1654 : 랜선 자르기

실버Ⅲ

 

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

//2805 나무자르기 문제와 유사
int main() {

	int k, n;
	scanf("%d%d", &k, &n);
	vector <long long> v;

	long long tmp;
	for (int i = 0; i < k; i++) {
		scanf("%lld", &tmp);
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	long long gaesoo;
	long long max_l = 1;

	long long low = 1;
	long long mid;
	long long high = v.back();

	//이분탐색으로 찾는것은 인덱스가 아닌 max_l값
	while (low <= high) {
		mid = (low + high) / 2;
		gaesoo = 0;
		for (int i = 0; i < k; i++) {
			gaesoo += v.at(i) / mid;
		}
		if (gaesoo >= n) {
			if (mid > max_l)
				max_l = mid;
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	printf("%lld", max_l);
}

 

이분 탐색의 원형은 선형 컨테이너에 해당 원소(target)가 있는지의 여부를 찾는 것이지만

이렇게 응용해서 조건을 만족하는 원소 x를 찾는 방법으로도 사용할 수 있다

 

이분 탐색의 응용이지만 이 로직은 많이 쓰이니까 머릿속에 꼭 입력해놔야 함

--------------------------------------------------------------------------------------------

2022.01.06 (SDS 중...)

 

이게 parametric search 구나..

다른 걸 알고있었네