백준 2805 나무 자르기 / C++

문제 : 2805

풀이 point

이진검색 법 parametic search(매개변수 탐색)을 활용한다.
O(N)으로 알고리즘을 짜도 시간초과가 일어날 경우 이 알고리즘을 의심해볼만 하다.
현재 M의 점위가 2억이기 때문에 O(N)이어도 시간초과가 일어난다.(보통 1억이 1초)

이때 나무 길이 M이 늘어날 수록 나무 N개의 개수는 계속 줄어든다. 이런 감소형태 그래프에서 이진검색을 통해 나무 N개의 개수를 만족하면서 나무 길이 M이 최대가 되는 값을 log(M)에 찾을 수 있다.

풀이 방법

이진검색을 통해 나무 N개의 개수를 만족하면서 나무 길이 M이 최대가 되는 값을 찾는다.

여기서 M의 범위는 1 <= M <= 2,000,000,000이지만 이진검색을 할때는 M의 최대 범위가 입력 받은 나무 중 가장 큰 크기이다.

코드

//백준 2805, 나무 자르기

#include <iostream>
#include <algorithm>

int N, M;
long long arr[1'000'000];

int solve(long long mid){
    long long ans{0};
    for(int i{0}; i<N; ++i){
        if(arr[i] > mid) ans += arr[i] - mid;
    }
    return ans >= M;
}

int main (){

    std::cin >> N >> M;
    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    std::sort(arr, arr+N);

    long long st{0}; long long end{arr[N-1]};
    while(st < end){
        long long mid = (st+end+1) / 2;
        if(solve(mid)) st = mid;
        else end = mid-1;
    }

    std::cout << st;

    return 0;
}