[C++] BAEKJOON 2805 나무 자르기

https://www.acmicpc.net/problem/2805

불러오는 중입니다...

이분탐색 을 활용하여 문제를 해결하였습니다.

높이 mid를 이분탐색으로 정한 후, 나무의 길이가 높이보다 크다면 잘라서 myTree 에 더해주었습니다. 이 값이 원하는 나무의 길이 M 보다 크다면 left 를 이동시켜 높이를 높여주고, M 보다 작다면 right 를 이동시켜 높이를 낮춰주며 가능한 최대 높이를 찾았습니다.

#include <iostream>

using namespace std;

int tree[1000000];

int main(){
    int N,M;
    cin >> N >> M;
    
    int maxTree = 0;
    
    for (int i=0;i<N;i++){
        cin >> tree[i];
        maxTree = max(maxTree, tree[i]);
    }
    
    long long left = 1;
    long long right = maxTree;
    
    int answer = 0;
    
    long long myTree = 0;
    
    while (left<=right){
        long long mid = (left+right)/2;
        
        myTree = 0;
        
        for (int i=0;i<N;i++){
            if (tree[i] > mid)
                myTree += tree[i]-mid;
        }
        
        if (M>myTree){
            right = mid-1;
        }
        else {
            left = mid+1;
            answer = mid;
            
        }
    }
    cout << answer << "\n";
}