백준1654 - 랜선 자르기

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

1654번: 랜선 자르기

이분탐색을 활용한 문제다. 현재 만들 수 있는 랜선의 갯수가 주어진 랜선의 갯수 이상이면 답을 갱신한다. 답을 찾으면 범위를 반으로 줄여 큰 쪽으로 탐색하기 때문에 현재 길이와 비교 과정이 없어도 가장 최근의 찾은 길이가 답이 된다. 

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

int main() {
	vector<int> v; //랜선의 길이
	int K, N;
	int num;
	int big = 0; //최댓값 찾는 변수
	unsigned long long int ans = 0; //만들 수 있는 최대 길이

	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> num;
		v.push_back(num);
		if (big < num) {
			big = num;
		}
	}

	//처음 값과 끝 값 설정
	unsigned long long int left = 1;
	unsigned long long int right = big;

	//길이 탐색
	while (left <= right) {
		unsigned long long int mid = (left + right) / 2ull; //현재 길이 설정
		unsigned long long int cnt = 0; //자를 수 있는 랜선의 갯수

		//현재 만들 수 있는 총 랜선의 수
		for (int i = 0; i < v.size(); i++) {
			cnt = cnt + v[i] / mid;
		}

		if (cnt >= N) { //현재 만들 수 있는 총 랜선의 수가 N 이상이면
			ans = mid; //현재 길이로 갱신
			left = mid + 1; //범위를 큰 쪽으로 줄임
		}
		else { //현재 만들 수 있는 총 랜선의 수가 N보다 작으면
			right = mid - 1; //범위를 작은 쪽으로 줄임
		}
	}

	cout << ans;
}