백준 2805 - 나무 자르기

1. 문제 정리
  - 앞에 풀었던 1654번 문제와 유사하다.

  - 각 나무의 높이 H가 주어진다. 정답인 값을 ans라고 하였을 때, ans 값 이상의 나무는 H-ans만큼 잘려간다.

  - 각 나무의 H - ans 값의 합이 M이상의 최솟값이 되도록한다.(Upper Bound)

 
2. 접근
  - 이번에도 이분탐색으로 풀고자 하였다.

  - 가장 큰 H값을 max, 그리고 min 값을 0으로 잡아 이분 탐색을 적용하고자 하였다.
 
3. 풀이

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

long m, n;
vector<long> a;
long lo = 0;
long hi = 0;
long ans = -1;

void bis(){
    while(lo <= hi){
        long mid = (lo + hi) / 2;
        long cnt = 0;
        for(long i: a){
            if(i > mid) cnt += i-mid;
        }
        if(cnt < m) hi = mid-1;
        else {
            lo = mid+1;
            if(ans < mid) ans = mid;
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=0; i < n; i++){
        long input;
        cin >> input;
        a.push_back(input);
        if(hi < input) hi = input;
    }
    bis();
    cout << ans;
}

  - int lo, hi : 이분탐색의 left 값과 right 값이다.

  - bis() 이후 이분탐색을 실행한다. Upper Bound이기 때문에 정답값에는 mid 값을 그대로 넣는다.
 
4. 소감

  - 사실 소감이라고 할 것도 없는게, 바로 직전에 풀었던 1654번과 거의 유사한 문제이다. 하지만 처음 1654번을 풀었을 때 보다 훨씬 접근이 수월했던 점에 있어, 좀 더 다양한 이분탐색 문제를 접해보면서 익숙해져갈 필요가 있을 거라 생각한다.