Parametric Search

Parametric Search란?

• 어떤 조건을 만족하는 값들 중에서 최대/최소 값을 이진 탐색을 통해 찾는 방법
• 탐색 대상이 정렬된 배열이 아니라, 숫자 범위 자체
• 주어진 조건을 만족하는지를 판단하는 판별 함수를 만들어야 함

중요 요소

범위 설정

• left - 최소 값
• right - 최대 값
• mid - 중간 값

판별 함수

• bool Can~~
• 조건 만족 시 -> 더 큰 값이 가능한 지 탐색
• 조건 불만족 시 -> 값을 줄여 범위 재조정

예시

https://www.acmicpc.net/problem/2805

#include <iostream>
#include <vector>

using namespace std;

// 잘라낸 값을 모두 합쳤을 때 N과 같거나 큰지 여부
bool can_cut(const vector<int> &woods, int len, int target)
{
    int remainder = 0;
    for (int i = 0; i < woods.size(); i++)
    {
        if (woods[i] >= len)
        {
            remainder += woods[i] - len;
        }
    }

    return remainder >= target;
}

int main(void)
{
    freopen("wood.txt", "r", stdin);
    int N;
    cin >> N;

    int need;
    cin >> need;

    vector<int> woods(N);

    for (int i = 0; i < N; i++)
    {
        cin >> woods[i];
    }

    int left = 1; // 자른 값은 1 이상이어야 하기 때문에 최소 값 1로 설정
    int right = *max_element(woods.begin(), woods.end()); // 가장 큰 나무 이상 값으로 자를 수 없기 때문에 가장 큰 나무가 최대 값으로 설정
    int answer = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (can_cut(woods, mid, need))
        {
            answer = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    cout << answer << endl;

    return 0;
}