C++ / 백준 / 1654 / 랜선 자르기

문제

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

1654번: 랜선 자르기

문제풀이

랜선의 최소 길이는 1, 최대길이는 가장 긴 랜선 길이로 둔다.

mid는 (min+max)/2로 두면서, mid 길이만큼 각 랜선들을 자르고 그 개수를 cnt변수에 저장한다.

랜선이 구하고자 하는 개수보다 적으면 더 짧게 잘라야 하므로 max길이를 mid-1만큼 줄인다.

반대로 랜선이 구하고자 하는 개수와 같거나 더 많으면 더 길게 자를 수 있는 경우를 생각해야 하므로 min길이를 mid+1 길이로 늘린다.

 

 

코드

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

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

	int K = 0, N = 0;
	cin >> K >> N;
	vector<int>lan(K, 0);
	int idx = 0;
	for (idx = 0; idx < K; ++idx)
		cin >> lan[idx];

	long long min_lan = 1;
	long long max_lan = 2147483647;

	while (min_lan <= max_lan) {
		long long mid_lan = (max_lan + min_lan) / 2;
		long long lan_cnt = 0;
		for (idx = 0; idx < K; ++idx)
			lan_cnt += (lan[idx] / mid_lan);
		if (lan_cnt < N)
			max_lan = mid_lan - 1;
		else
			min_lan = mid_lan + 1;
	}
	cout << max_lan;
}