백준 2805번: 나무 자르기

문제

문제 바로가기> 백준 2805번: 나무 자르기

풀이

binary search를 이용해 나무를 어느 지점에서 잘라야 가장 좋은지 그 위치를 알아내는 방식으로 문제를 풀었다. 이분 탐색이지만 따로 정렬은 필요하지 않고, 입력 받을 때 최대 나무 높이를 이용해서 이분 탐색을 진행하면 된다. 주의 해야할 점은 low+high가 int 범위를 넘어설 수 있으니 long long type으로 선언해주기...!

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m, tmp; cin>>n>>m;
    vector<int> v;
    int low=0, high=0;
    for(int i=0; i<n; i++){
        cin>>tmp;
        if(high<tmp) high=tmp;
        v.push_back(tmp);
    }
    while (low<=high){
        long long mid = (low+high)/2;
        long long cutoff = 0;
        for(int i=0; i<n; i++){
            if(v[i]>mid) cutoff+=v[i]-mid;
        }
        if(cutoff>=m) low = mid+1;
        else high = mid-1;
    }
    cout << high;
}