Parametric search algorithm, 2805 백준

알고리즘 분석

파라메트릭 서치 알고리즘이란?

In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique for transforming a decision algorithm (does this optimization problem have a solution with quality better than some given threshold?) into an optimization algorithm (find the best solution).

 -> 결정 알고리즘을 최적화 알고리즘으로 변형해주는 알고리즘이다.

이때 결정 문제를 해결하여 최적의 값을 얻기 위해소서는 정답의 후보군이 정렬되어있어야하고, 각 원소들에 대해서 결정함수(최적의 값 X'가 현재의 값 X보다 큰가? 같은가? 작은가? 를 결정해주는 함수)가 정의되어 있어야 한다.

정리하자면 모든 정답 후보군 중에서 이분탐색과 같이 중앙의 값을 선택하고 그 값에 대하여 결정 알고리즘을 시행 한 후 시행한 결과에 따라 정답 후보군을 조정한다. 이 과정을 여러번 반복한다.

 

문제

문제 분석

문제의 요점은 input[i]  > x 인 모든 i에 대하여 sum(input[i]-x) >= m을 만족하는 x의 최댓값을 구하는 것이다.

그렇다면 정답의 후보군은 어떻게 될까? 문제에 따르면 "모든 나무의 길이의 합이 m보다 같거나 클것이다." 라는  구절로 인해 최소 후보값은 0일것이고 "M>=1"이라는 조건에 의하여 최대 후보값은 input_max-1일것이다.

그렇다면 input[i]  > x 인 모든 i에 대하여 sum(input[i]-x)을 A라고 할 때, A >= m이라면 A의 값을 줄여야 하고(즉, 자르는 높이의 최소범위를 높여야 한다), A<m이라면 A의 값을 높여야 한다(즉, 자르는 높이의 최대 범위를 낮춰야 한다.)

이를 이분탐색을 이용하여 더 빠르게 풀어보았다. (안쓴다면 O(N)이지만, 쓰면 O(logN), 입력 후보 범위가 매우 크므로 유의미 할 것이다)

내가 생각할 때 파라메트릭 서치의 가장 중요한 포인트는 두가지 인것 같다.

1. 정답 범위 산정

2. 결정 알고리즘의 구현

3. 결정 알고리즘을 통한 범위 적용

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
vector<lld> input_v;
lld n,m;

lld param_search(lld param_min, lld param_max)
{
    lld now_min = param_min;
    lld now_max = param_max;
    lld tmp_m = 0;
    while(now_min <= now_max)
    {
        lld mid = (now_min + now_max)/2;
        lld now_m = 0;
        for(lld i=0; i<input_v.size(); i++)
        {
            if(input_v[i] > mid)
                now_m += (input_v[i] - mid);
        }

        if(now_m < m)
            now_max = mid-1;
        else if(now_m >= m)
        {
            tmp_m = max(tmp_m, mid);
            now_min = mid+1;
        }
    }
    return tmp_m;
}

void solution()
{
    // code
    cin >> n >> m;
    lld input_max = 0;
    for(int i=0; i<n; i++)
    {
        lld tmp;
        cin >> tmp;
        input_max = max(input_max, tmp);
        input_v.push_back(tmp);
    }
    cout << param_search(0, input_max);
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

값의 범위를 좀만 더 자세히 봐야겠다.

난이도가 낮다고 대충 넘기지 말고 모든 값에 대하여 나타날 수 있는 값을 생각한 후 자료형을 결정하자.