[BOJ. 1654] 랜선 자르기

1. 링크 백준 1654 랜선자르기

2. 풀이

가지고 있는 랜선의 개수 K개에서 필요한 랜선의 개수 N개로 만들 때 랜선의 최대 길이를 구하는 문제입니다.

여기서 우리가 주목해야 할 점은 랜선의 길이(출력 값)로 만들 수 있는 랜선의 개수(N)를 구하기 쉽다는 점입니다. 이는 결국 Brute force로도 실행시간만 충분하다면 답을 구할 수 있다는 것을 의미합니다.

하지만 이 문제는 실행시간이 제한되어 있습니다. 그렇다면 최적화가 필요하다는 것인데 무엇을 이용하면 최적화를 할 수 있을까요?

정답은 랜선의 길이(출력 값)이 커짐에 따라서 랜선의 개수(N)가 감소하는 점을 이용하면 됩니다.
ex) 랜선의 길이가 200이면 N은 11, 랜선의 길이가 150이면 N은15

이는 랜선의 길이에 대해 랜선의 개수(N)가 오름차순으로 정렬되어 있다는 것을 의미합니다. 이는 우리가 이분탐색을 쓸 수 있다는 것을 의미합니다.

3. 주의할 점

1. 수의 범위에 대해서 제대로 알 것

   • 문제의 설명에서 랜선의 길이가 2³¹ - 1보다 작거나 같은 자연수라고 int를 쓰면 이분탐색을 하는 과정에서 mid = (left + right) / 2를 하는 과정에서 Overflow가 발생할 수가 있으므로 long long을 자료형으로 쓰는 것이 중요합니다.

2. 파라매트릭 서치(Parametric Search)에 대해서 제대로 알기

   • 다음은 정렬된 배열 arr에서 target보다 큰 수 중에서 가장 가까운 수를 찾는 함수 findClosestMinimum,

   • target보다 큰 작은 중에서 가장 가까운 수를 찾는 함수 findClosestMaximum 입니다.

int findClosestMinimum(int target, vector<int> &arr)
{
    int left = arr[0];
    int right = arr[arr.size() - 1];

    while (left < right)
    {
        int mid = (left + right + 1) / 2;
        if (target <= mid)
        {
            left = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
    return left;
}

int findClosestMaximum(int target, vector<int>& arr)
{
    int left = arr[0];
    int right = arr[arr.size() - 1];

    while (left < right)
    {
        int mid = (left + right) / 2;
        if (target >= mid)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return right;
}

보시다 싶이 최대 값을 찾을 때와 최소 값을 찾을 때, 새롭게 mid를 설정하는 부분과 right와 left를 갱신하는 부분이 조금 다르다는 것을 알 수 있습니다. 이에 대한 자세한 설명은 아래의 링크를 참고해주시기 바랍니다.

파라매트릭 서치(parametric search)

4. 코드

#include <iostream>
#include <vector>

using namespace std;

const long long MAX = 1LL << 31;

void input(vector<int>& lines, int k)
{
    for (int i = 0; i < k; i++)
    {
        cin >> lines[i];
    }
}

bool isPossible(vector<int>& lines, long long mid, long long N)
{
    long long count = 0;
    for (int i = 0; i < lines.size(); i++)
    {
        count += lines[i] / mid;
    }

    if (count >= N)
        return true;
    else
        return false;
}

long long parametric_search(vector<int>& lines, long long N)
{
    long long left = 1;
    long long right = MAX;

    while (left < right)
    {
        long long mid = (left + right + 1) / 2;

        if (isPossible(lines, mid, N))
        {
            left = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
    return left;
}


int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int K;
    int N;

    cin >> K >> N;
    vector<int> lines(K);
    input(lines, K);
    cout << parametric_search(lines, N) << '\n';
}