[알고리즘] 랜선 자르기

구현 방식

• 결정문제로 이분 탐색으로 풀 수 있다.
• 이분 탐색으로 현재 탐색하고 있는 midSize 길이로 N개 이상으로 랜선을 자를 수 있는지 확인
• 확인후 N개 이상으로 자를 수 있다면 minSize 를 midSize + 1 로 변경해서 더 큰걸로 자를 수 있는지 확인
• N개 이상으로 자를 수 없다면 maxSize 를 midSize - 1로 변경해서 더 작은걸로는 자를 수 있는지 확인

void solution(int K, int N, vector<int> inputs){
    long long inputsSum = 0;
    for (vector<int>::iterator it = inputs.begin(); it != inputs.end(); it++)
    {
        inputsSum += *it;
    }
    long long minSize = 1; // left
    long long maxSize = inputsSum / N; // right
    long long midSize = (minSize + maxSize) / 2;

    while (minSize <= maxSize )
    {
        if (canCutWithN(N, midSize, inputs))
        {
            minSize = midSize + 1;
            midSize = (minSize + maxSize) / 2;
        }
        else
        {
            maxSize = midSize - 1;
            midSize = (minSize + maxSize) / 2;
        }
    }

    cout << midSize;
}


bool canCutWithN(int N, long long size , vector<int>& inputs)
{
    long long count = 0;
    for (vector<int>::iterator it = inputs.begin(); it != inputs.end() ; it++)
    {
        long long wireSize = *it;
        count += (wireSize / size);
    }

    return count >= static_cast<long long> (N);
}