[BOJ] 1654 랜선 자르기

문제: https://www.acmicpc.net/problem/1654

 

 

문제 풀이:

binary search 알고리즘을 이용하여 가능한 최대 길이를 찾는다.

 

소스 코드:

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

typedef long long ll;
ll k, n,arr[10002];
ll sum;

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

	cin >> k >> n;

	for (int i = 0; i < k; i++) cin>>arr[i];

	ll l = 1, r = pow(2,31)-1;
	ll res = 0;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		sum = 0;
		for (int i = 0; i < k; i++) {
			sum += arr[i] / mid;
			if (sum > n) break;
		}
		if (sum >= n) {
			res = max(res, mid);
			l = mid + 1;
		}
		else r = mid-1;
	}
	cout << res << '\n';
	return 0;
}