[Baekjoon,1654] 랜선 자르기

해결

0부터 2^31-1까지 랜선의 길이를 이분 탐색했다. 현재 길이를 통해 n개의 개수를 채울 수 있으면 lo를 mid로, 채울 수 없으면 hi를 mid로 설정하는 방식이다.

구현 시 주의할 점은 주어진 랜선의 길이가 2^31-1 이라 범위가 벗어날 수 있어 int 대신 long으로 값을 저장하고 탐색해야 한다.

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

const int MAX_K=10000;

int k,need;
long length[MAX_K];

// 길이가 num일때 need개의 랜선을 만들 수 있는 가? 
bool canMake(long num)
{
    int count=0;
    for(int i=0;i<k;++i)
        count+=length[i]/num;
    return count>=need;
}

// 이분 탐색하여 최대 값을 구한다. 
long getMaxLength()
{
    long lo=0, hi=LONG_MAX;
    while(lo<hi-1)
    {
        long mid=(lo+hi)/2;
        if(canMake(mid))
            lo=mid;
        else
            hi=mid;
    }
    return lo;
}

int main()
{
    cin>>k>>need;
    for(int i=0;i<k;++i)
        scanf("%ld",&length[i]);
    
    cout<<getMaxLength();
    return 0;
}