2805 : 나무 자르기 (C++)

2805번: 나무 자르기

---

이분탐색... 어려워

#include<iostream>

using namespace std;

int N, M;

int main() {
    cin >> N >> M;

    int tree[N];
    int maxTree = 0;

    for(int i = 0; i < N; i++) {
        cin >> tree[i];
        maxTree = maxTree < tree[i] ? tree[i] : maxTree;
    }

    int left = 1; // 시작값
    int right = maxTree; // 최대값
    long long int cnt;
    int mid;
    int result = 0;

    while(left <= right) {
        mid = (left + right) / 2;
        cnt = 0;
        
        for(int i = 0; i < N; i++) {
            if(mid <= tree[i]) {
                cnt += tree[i] - mid;
            }
        }

        if(cnt >= M) { // 적어도 M미터 이상의 나무를 가져갈 수 있을 때.
            left = mid + 1;
            result = max(result, mid); // 높이의 최대값
        } else if(cnt < M) {
            right = mid - 1;
        }


    }

    cout << result << endl;

    return 0;
}