[C++] BOJ-1654

 

문제풀이

---

1. 이분탐색 문제이다. 숫자의 범위가 int형이 훨씬 넘어가니 long long 형을 써야한다.

 

2. 가장 큰 랜선을 기준으로 시작하여 이분탐색으로 필요한 랜선의 수에 맞는 최적의 길이를 찾아야한다.

 

3. sum이 N보다 크거나 같으면 start = mid + 1, 그렇지 않으면 end = mid-1이 되게하여 점차 범위를 줄여나가는 방식으로 접근했다.

 

#include <iostream>

using namespace std;


int main(){
	ios_base::sync_with_stdio(0);
  	cin.tie(0);
	long long K,N;
	
	cin >> K >> N;
	
	long long wire[10000];
	long long start = 1, end, mid;
	long long result = 0;
	
	for(int i = 0; i<K; i++){
		cin >> wire[i];
		if(end < wire[i]) end = wire[i];
	}
	
	
	while(start <= end){
		mid = (start+end)/2;
		long long sum = 0;
		
		for(int i = 0; i<K; i++){
			sum += wire[i]/mid;
		}
		
		if(sum >= N){
			start = mid+1;
			if(mid > result){
				result = mid;
			}
		}else{
			end = mid-1;
		}
	}
	
	cout << result;
}