이분 탐색의 응용(Parametric Search)

이분 탐색을 간단히 배열에서 숫자를 찾는 정도로만 알고있는 사람들이 많을 것입니다.

그러나 이분 탐색을 응용하면 최댓값을 구하는 문제나 최솟값을 구하는 문제를 거의다 풀 수 있습니다.

다음 소스와 문제를 보면서 이해하기를 바랍니다.

bool Can(long long x, long long num) {
    if (x >= M) return false;
    return (1 + x)*x / 2 <= num;
}
 
int main() {
    int q;
    long long x, l, r, mid;
 
    scanf("%d", &q);
    while (q--) {
        scanf("%lld", &x);
        
        l = 1, r = x;
        while (l <= r) {
            mid = (l + r) / 2;
            if (Can(mid,x)) l = mid + 1;
            else r = mid - 1;
        } printf("%lld\n", l - 1);
    }
}

문제 보기: 백준 11561번 - 징검다리