백준 1654 - 랜선 자르기

• 1654 : 랜선 자르기

Parametric Search를 위해서 풀어본 문제이다.
Parametric Search는 주어진 범위가 매우 큰 수 일 때 주로 사용한다. 따라서, start와 end의 자료형을 long long으로 두어야 한다!

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

int k = 0, n = 0, ans = 0;
void parametric_search(vector<int> wires) {
	long long start = 1;
	long long end = *max_element(wires.begin(), wires.end());

	while (start <= end) {
		long long mid = (start + end) / 2;
		int pieces = 0;

		for (int wire : wires)
			pieces += wire / mid;

		if (pieces >= n) {
			start = mid + 1;
			if(ans < mid) ans = mid;
		}
		else end = mid - 1;
	}
}

int main() {
	cin >> k >> n;
	
	vector<int> wires(k, 0);
	for (int i = 0; i < k; i++)
		cin >> wires[i];

	parametric_search(wires);
	cout << ans;
	return 0;
}