백준 1654번:랜선 자르기

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

1654번: 랜선 자르기

 

이 문제는 랜선의 길이를 구해야한다. 랜선의 길이 최댓 값을 구하기 위해 이분 탐색을 이융했다.순차 탐색을 하기에는 시간 초과가 나와 더 효율적인 이분탐색을 썻다.

랜선의 길이는 당연히 정렬 되어 있기에 이분탐색을 쓸 수 있고 랜선의 길이가 크면 랜선갯수는 적게 나오고 작으면 더 많이 나온다.

즉 n보다 크거나 같다라는 조건을 만족하면 left값을 mid+1로 지정하고 만족하지 않으면 right를 mid-1로 지정하면 된다.그러면 최대인 랜선값이 나온다.

코드를 보장

#include <iostream>
#include <vector>
using namespace std;
long long k,n;
bool check(vector<int>& v,long long x){           //x이 값이 n보다 작은지 아닌지 판단 
    long long cnt=0;
    for(int i=0;i<k;i++){
        cnt+=(v[i]/x);
    }
    return cnt>=n; 
int main(){
    cin>>k>>n;
    long long max=0;
    vector<long long> v(k);
    for(int i=0;i<k;i++){
        cin >> v[i];
        if(max<v[i]){
            max=v[i];
        }
    }
    long long ans=0;
    long long left=1;
    long long right=max;
    while(left<=right){                       //랜선 길이 구하기 위한 이분탐색
        long long mid=(left+right)/2;
        if(check(v,mid)){                    //mid값이 n보다 작지 않으면 길이 최대값 구하기위해 left를 mid+1지정
            if(ans<mid){
                ans=mid;
            }
            left=mid+1;
        }
        else{                               //mid값이 n보다 작으면 n보다 커져야하기 때문에 right=mid-1지정
            right=mid-1;
        }
    }
    cout <<ans;

}