[백준/c++] 1654 랜선 자르기

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

이분탐색으로 풀 수 있는 문제이다.

초기값(start)는 1로 두고, 마지막값(end)은 sort한 벡터 마지막 값으로 설정한다. 

 

이분탐색을하기 위해서는 무조건 오름차순으로 정렬하고 해야한다.

 

K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이기 때문에 int값은 long long타입으로 설정해야한다. 

 

또한, 최대 길이를 구해야하기 때문에 sum==n이더라도 계속해서 값을 갱신해서 저장을 해야한다. 

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

int main() {
	int k, n;
	cin >> k >> n;

	vector<int> v;

	for (int i = 0; i < k; i++) {
		int k;
		cin >> k;
		v.push_back(k);
	}
	sort(v.begin(), v.end());
	long long int start = 1;
	long long int end = v[v.size() - 1];
	long long int answer = 0;

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

		long long int sum = 0;
		for (int i = 0; i < v.size(); i++) {
			sum += v[i] / mid;
		}
		if (sum >= n) {
			answer = mid;
			start = mid + 1;	//더 긴 길이 시도
		}
		else
			end = mid - 1;
	}
	cout << answer;
}