[백준] 1654 랜선 자르기

백준1654링크

기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성

입력

이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다.
K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. (항상 K ≦ N)
그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다.
랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

출력

N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력

풀이

• 이분탐색
  -랜선의 길이가 2^31-1이기 때문에 계산 도중 정수의 범위가 넘어갈 수도 있기 때문에 unsigned int로 설정 (long 사용해도 가능할듯)
  -만들 수 있는 랜선의 수 = 랜선 길이 / 나누려는 길이

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;


int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    unsigned int K,N,input,result=0;
    cin>>K>>N;
    vector<int> v;
    for(unsigned int i=0;i < K;i++){
        cin>>input;
        v.push_back(input);
    }
    
    unsigned int end=*max_element(v.begin(),v.end());
    unsigned int start=1,mid,total;
    
    while(start<=end){
        total=0;
        mid=(start+end)/2; 
            for(unsigned int i=0;i < K;i++){
                if(v[i]>=mid){
                    total+=(v[i]/mid); //만들 수 있는 랜선의 수
                }
            }
        
        if(total<N){
            end=mid-1;
        }else{ //만든 랜선의 수가 N이상이 되는 경우 -> 조건 만족
            result=max(result,mid); //최대값 비교
            start=mid+1;
        }
    }
    cout<<result<<"\n";
    return 0;
}