[백준 2805번] [이분탐색] 나무 자르기

이 문제에서 어차피 0부터 나무의 최대높이까지만 살피면 되는 상황이므로 이분탐색을 활용하여 자르는 높이를 구하는 것이 훨씬 쉽다는 것을 파악하면 된다.

 

다만, 이 문제를 처음에 풀었을 때 틀렸는데 compare_value가 int의 범위를 넘을 수 있다는 것을 확보하지 못했다.

대략적으로 지금 문제 조건이 간당간당하게 int범위를 넘지 않는 상황이므로 더하다보면 해당 범위를 넘을 수 있다. 이것만 주의해서 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    int n, m;
    cin >> n >> m;
    vector<int> tree_length_store;

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        tree_length_store.push_back(temp);
    }
    sort(tree_length_store.begin(), tree_length_store.end());
    int start = 0;
    int end = tree_length_store[n - 1];
    int mid;
    int result;

    while(start != end){
        mid = (start + end) / 2;
        long long compare_value = 0;
        for(int i = 0; i < n; i++){
            if(tree_length_store[i] > mid){
                compare_value += tree_length_store[i] - mid;
            }
        }
        if(compare_value >= m){
            result = mid;
            start = mid + 1;
        }
        else end = mid;
    }

    cout << result << "\n";
    return 0;

}