백준 1654번: 랜선 자르기

문제

문제 바로가기> 백준 1654번: 랜선 자르기

풀이

binary search를 이용해서 풀었다. low+high가 int 범위를 벗어날 수 있기 때문에 datatype을 long long으로 설정해주어야 한다.

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

int main(){
    int k, n; cin>>k>>n;
    int cable[k];
    for(int i=0; i<k; i++)
        cin>>cable[i];
    sort(cable, cable+k);
    long long low = 0, high = cable[k-1];
    long long mid = (low+high)/2;

    while (low<=high){
        int num = 0;
        for(int i=0; i<k; i++){
            if(mid==0) mid=1;
            num+=cable[i]/mid;
        }
        if(num<n) high = mid-1;
        else low = mid+1;
        mid = (low+high)/2;
    }
    if(n==1) cout << cable[0];
    else cout << mid;   
}