1654번: 랜선 자르기

1654번:  랜선 자르기

사용 언어: C++

 

풀이

2110번: 공유기 설치와 유사한 문제다. 

최소 길이는 1, 최대 길이는 가장 긴 랜선의 길이로 잡는다. 이분 탐색으로 canCut(mid)를 해서 각 랜선을 mid == length 길이만큼 잘라서 나오는 개수가 N개 이상이면 true, 아니면 false. True가 리턴되면 low = mid +1 해서 더 긴 길이가 가능한지 확인하고, false면 high = mid - 1로 더 짧은 길이에서 가능한지 확인한다.

다만, 유의할 점은 이 문제는 변수들이 int로 해결이 안된다는 점이다. 

문제에서 "랜선의 길이는 2^31보다 작거나 같은 자연수이다." 라고 랜선의 길이가 int 값보다 작다고 주어지긴 하지만, mid = (low + high) / 2를 할 때 low + high가 int 값을 넘어서면서 오브플로우가 발생할 수 있기 때문이다.

따라서, mid를 long long으로 선언하고, low = mid + 1;과 high = mid - 1; 도 있으므로 low와  high도 long long으로 선언해준다. 그러면 canCut에 long long인 mid를 넘겨주므로 canCut의 모둔 변수도 long long으로 선언해줘야한다.

 

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

int K, N;
vector<long long> cables;

// 주어진 길이로 랜선을 N개 이상 만들 수 있는지 확인
bool canCut(long long length)
{
    long long count = 0;
    for (int i=0; i<K; i++)
    {
        count += cables[i] / length;  // 각 랜선을 length로 잘랐을 때 나오는 개수
    }
    return count >= N;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> N;
    cables.resize(K);

    for (int i = 0; i < K; i++)
    {
        cin >> cables[i];
    }

    long long low = 1;
    long long high = *max_element(cables.begin(), cables.end());  // 가장 긴 랜선의 길이
    long long answer = 0;

    // 이분 탐색 시작
    while (low <= high)
    {
        long long mid = (low + high) / 2;

        if (canCut(mid))
        {
            answer = mid;  // 현재 길이로 N개 이상 가능하면 일단 저장
            low = mid + 1;  // 더 긴 길이로 시도
        }
        else
        {
            high = mid - 1;  // 랜선의 개수가 부족하면 더 짧은 길이로 시도
        }
    }

    cout << answer << "\n";
    return 0;
}