[BOJ] 1654번 | 랜선 자르기 (C++)

🔗문제 보러가기

1654번: 랜선 자르기

 

🧑🏻‍💻풀이 과정

K개의 랜선들을 잘라, 동일한 길이로 N개 이상을 만든 경우의 수들 중 가장 긴 단위 길이를 찾으면 되는 문제입니다.

매개변수 탐색(Parametric Search)을 이용하여 풀 수 있습니다. 사실 매개변수 탐색이란 용어를 오늘 처음 들어봤는데, 내용을 보니 제가 알게 모르게 사용했던 방법이더군요.

 

알고리즘은 간단합니다.

1. 배열(arr)에 저장되어 있는 K개의 랜선들을 오름차순 기준으로 정렬합니다.
2. 이진 탐색(Binary Search)을 응용하여 탐색을 시작할 겁니다.
   • left는 가장 작은 길이(1), right는 가장 긴 길이(arr[K-1])의 값을 가집니다.
   • left \( \leq \) right가 될 때까지, 다음을 반복합니다.
     • mid = (left + right) / 2 값을 구합니다.
     • K개의 케이블을 차례대로 돌며, mid 단위로 잘랐을 때의 개수(cable / mid)를 누적해 저장합니다.
     • 그렇게 얻은 총 개수가 N개 이상이면, left = mid + 1로 두고 해당 개수는 별도로 저장해둡니다.
     • 아니라면, last = mid - 1로 둡니다.
3. 위의 이진 탐색을 통해 얻은 결과를 출력합니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <algorithm>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
using uint32 = unsigned int;

uint32 FindLongestCableLength(const vector<int>& cables, const int N)
{
    uint32 start = 1, last = cables.back();
    uint32 answer = 0;

    while (start <= last)
    {
        uint32 mid = (start + last) / 2;
        uint32 count = 0;

        for (const auto& cable : cables)
            count += (cable / mid);

        if (count >= N)
        {
            answer = mid;
            start = mid + 1;
        }

        else
            last = mid - 1;
    }

    return answer;
}


int main()
{
    FAST_IO;

    int K, N;
    cin >> K >> N;

    vector<int> lanCables(K);
    for (int i = 0; i < K; i++)
        cin >> lanCables[i];

    sort(lanCables.begin(), lanCables.end());
    int answer = FindLongestCableLength(lanCables, N);

    cout << answer;
    return 0;
}

 

랜선의 최대 길이가 \( 2^{31} - 1 \)이라고 했으므로, int 자료형은 mid를 구하는 과정에서 오버플로우가 날 수 있습니다.

이는 unsigned int를 사용하거나, long long을 사용하여 해결할 수 있습니다.

 

그리고 의아했던 게, answer = max(answer, count)를 하지 않아도 정답 처리가 되더라구요. 희한하네요.