[C++] 백준 1654번 - 랜선 자르기

 

 

문제 1654번

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

1654번: 랜선 자르기

 

'최대' 이런 단어가 있는 거 보니 이분 탐색으로 풀면 될 것 같다. 입력된 길이 중에서 가장 긴 길이를 maxx에 넣어준다. 그리고 start는 1, end는 가장 긴 길이로 초기화해준다. while문을 이용해 start<=end일 동안 반복해준다. 벡터에 넣어둔 랜선의 길이들을 mid값으로 나눈 후 그 값들을 다 더해서 K가 되는지 확인한다. K개보다 많이 만들어도 K개 만드는 것에 포함되기 때문에 합한 sum값이 K보다 작으면 end를 1감소시켜주고, 아니면 해당 mid값을 result에 넣고 start를 1증가시켜준다.

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

long long K, N;
vector <int> v;

int main() {
	cin >> N >> K;
	long long maxx = 0;
	int a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		v.push_back(a);
		if (maxx < a) {
			maxx = a;
		}
	}
	long long result;
	long long start = 1, end = maxx;
	while (start <= end) {
		long long mid = (start + end) / 2;
		int sum = 0;
		for (int i = 0; i < N; i++) {
			sum += v[i] / mid;
		}
		if (sum < K) {
			end = mid - 1;
		} else {
			result = mid;
			start = mid + 1;
		}
	}
	cout<<result;

	return 0;
}