백준[2805] 나무 자르기

해당 문제는 백준[1654] 랜선 자르기와 매우 흡사한 문제이다.

 

재귀함수를 이용하면 코드가 간결해져서 쉽지만

시간초과가 날까 봐 재귀함수를 사용하지 못하겠다ㅜ

 

#include <bits/stdc++.h>

int findMaxBranches(vector<int> &arr, int M, int start, int end){
    int result = 0;
    
    while(start<=end){
        int mid = (start+end)/2;
        long long total = 0;
        for(int i=0;i<arr.size();i++)
            if(arr[i] >= mid)
                total += arr[i] - mid;
        
        if(total >= M){
            result = mid;
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
        
    }
    return result;
}

void cutTree(){
    int N,M;
    scanf("%d%d",&N,&M);
    
    vector<int> arr;
    for(int i=0;i<N;i++){
        int n;
        scanf("%d",&n);
        arr.push_back(n);
    }
    sort(arr.begin(),arr.end());
    
    printf("%d\n",findMaxBranches(arr, M, 1, arr[N-1]));
    
}