[백준 1654] 랜선 자르기

오랜만에 파라메트릭 서치 문제를 풀었습니다.

파라메트릭 서치 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 문제입니다.

 

주어진 문제는 여러 개의 랜선의 길이가 주어졌을 때, 각 랜선들을 mid로 자르면 나눠지는 랜선의 개수가 N개 이상을 만들면 되는데, 이때 mid의 길이를 가능한 최대로 뽑고 싶다는 것이 이 문제의 핵심입니다.

 

예시에서는 200m로 잘랐을 때 11개를 만들 수 있으며 나올 수 있는 최대 길이라고 합니다.

어떻게 11개가 나왔을까요.

802 / 200 = 4

743 / 200 = 3

457 / 200 = 2

539 / 200 = 2

4 + 3 + 2 + 2 = 11개가 됩니다.

 

정리하면 어떻게 자르든 11개 이상만 나오면 조건을 만족하며, 그때 자른 길이 중 최대를 저장하면 됩니다.

만약에 조건 11개를 만족하더라도 200보다 작을 수 있는 경우의 수가 존재할 수 있습니다.

무슨 말이냐면, 

802 / 199 = 4

743 / 199 = 3

457 / 199 = 2

539 / 199 = 2

4 + 3 + 2 + 2 = 11개

어떤가요. 주어진 조건을 만족하면서도 자른 길이가 199m입니다.

 

정답이 한 가지가 아니라 여러 가지라는 뜻이죠.

즉 우리는 조건을 만족하더라도 더 최대로 자를 수 있는 경우가 있으면 그것이 정답이라는 뜻입니다.

조건을 만족한다! 더 길게 잘라볼까?????

조건을 만족하지 못한다! 좀만 적게 잘라보자...

 

약간 실생활을 생각해보면 됩니다.

이정도 자르면 4개는 나오겠지??

싹둑, 어라? 3개네 좀 더 짧게 잘라야겠다!

이런 경험이 있을 것입니다.

 

이렇게 조건을 만족하더라도 더 가보자!!처럼 이러한 방식을 파라메트릭 서치라고 합니다!

 

자르는 방법은 다음과 같습니다.

len의 길이로 자른다고 가정했을 때 나오는 개수를 우리는 아래와 같이 작성할 수 있습니다.

bool calc(int len)
{
    int cnt = 0;
    for(int i = 0; i < K; i++)
    {
        cnt += v[i] / len;
    }
    
    return cnt >= N;
}

랜선의 길이가 2^31 - 1보다 작거나 같은 자연수이기 때문에 이 말은 곧 0부터 int의 최댓값까지 나올 수 있다는 말이므로.

우리가 자르고자 하는 길이의 탐색 구간은 0 ~ INT_MAX까지! 

자연수라고 했으니까 0이 아니고 1로 해도 됩니다.

그런데 여러 문제를 풀어보니까 0이 실수도 안 하고 그렇습니다.

 

기존의 이진 탐색처럼 반복문을 구성하고 해당 mid(자를 길이)를 선택했다면 그걸로 잘라보고,

조건을 만족한다면 더 나아가 보고 (여기서 나아간다는 뜻은 길이를 더 길게 잘라보겠다는 뜻)

조건을 만족하지 못한다면 더 짧게 잘라보고

하면서 길이를 갱신해나가면 됩니다.

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

int K, N;
vector<int> v;

bool calc(int len)
{
    int cnt = 0;
    for(int i = 0; i < K; i++)
    {
        cnt += v[i] / len;
    }
    
    return cnt >= N;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K >> N;
    v.resize(K);
    for(int i = 0; i < K; i++) cin >> v[i];
    long long left = 0;
    long long right = INT_MAX;
    long long ans = 0;
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        if(calc(mid))
        {
            ans = max(ans, mid);
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    
    cout << ans << endl;
    return 0;
}