파라메트릭 서치(Parametric Search)

귀여운 새

 오늘은 파라메트릭 서치입니다.

이진 탐색을 응용하여 최적화 문제를 결정 문제로 바꾸어서 풀이하는 방법입니다.

사실 문제 상황을 살짝 변형하여 이진 탐색을 사용하는 것일 뿐입니다..

 

 

[백준 1654: 랜선 자르기] 문제를 통해 파라메트릭 서치가 무엇인지 알아봅시다.

 

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

 

 일단 가장 간단한 방법을 생각해봅시다.

자르는 랜선의 길이를 1부터 시작해서, 계속 N개 이상의 랜선이 만들어질때까지 랜선의 길이를 1씩 늘려봅니다.

이때의 길이를 m이라고 합시다.

그러다가 N개 미만의 랜선이 만들어지는 순간이 온다면, m-1이 최대 랜선의 길이가 되겠죠.

그런데, 이건 너무 비효율적입니다. 조금 더 효율적인 방법을 생각해봅시다.

 

 아까 전, 최대 랜선 길이를 구한 방법은 완전 탐색이라고 볼 수 있습니다.

그렇다면, 이진 탐색을 사용할 수 는 없을까요?

우선 이진 탐색을 이용할 수 있는지 생각해봅시다.

저희가 찾는 수는, N개 이상의 랜선을 만들 수 있는 최대의 길이 m입니다.

그리고, 저희가 탐색을 진행하는 범위는 1~..로 오름차순으로 정렬되어있네요.

정렬되어 있기 때문에 이진 탐색을 사용할 수 있을 것 같습니다.

그런데, N개 이상의 랜선이 안 만들어지는 경우는 확실히 m이 현재 값보다 이하임을 알 수 있는데

N개 이상의 랜선이 만들어지는 경우는 m이 현재 값인지, 아니면 그 이상인지 어떻게 판단해야 할까요?

 

 답은 현재 값+1도 함께 테스트해보는 것입니다.

만약 현재 값이 m이라면, 현재 값+1은 N개 이상의 랜선을 만들지 못할 것이고, 현재 값이 m보다 작다면

현재 값+1 또한 N개 이상의 랜선을 만들 수 있을 것입니다.

 

소스 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

long long l[10000];
long long k,n;

long long bi_search(long long s, long long e,long long q)
{
    long long t=(s+e)/2;
    long long i;
    long long sum=0;
    long long msum=0;
    for(i=0;i<k;i++)
    {
        sum=sum+l[i]/t;
        msum=msum+l[i]/(t+1);
    }
    if(sum>=n)
    {
        if(msum<n)
        {
            return t;
        }
        else
        {
            return bi_search(t+1,e,q+1);
        }
    }
    else
    {
        return bi_search(s,t-1,q+1);
    }
}
int main()
{
    long long i,j;
    cin >> k >> n;

    for(i=0;i<k;i++)
    {
        scanf("%d",&l[i]);
    }

    sort(l,l+k);
    cout << bi_search(1,l[k-1],0) << endl;

    return 0;
}

 소스코드가 많이 더럽습니다

 

 파라메트릭 서치는 보통 단독 문제로 나오기 보다는, 다른 알고리즘들을 사용하는 문제에서 사용하도록

나오는 경우가 많습니다. 따라서, 파라메트릭 서치를 어디에 사용할 수 있을지 잘 캐치하는 능력이 중요할 것 같습니다.

 

 

 학교에서 정신 없이 쓰느라 잘 설명한지 모르겠네요.. 원래는 난이도 순서대로 알고리즘을 소개하려고 했으나, 이미 여러 분들이 너무 잘 설명하신 것 같고, 제가 그 분들처럼 설명할 자신이 없어서 그냥 하고싶은 순서대로 하기로 결정했습니다... 그럼 다음 게시물로 돌아오겠습니다~~