[Silver 2] 2805 나무 자르기

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

 

배열에 잘라야할 나무를 담는다. 이후 배열을 정렬한다.

정렬하는 이유는 자를 수 있는 최대 높이를 구해야하기 때문이다.

 

자를 최소 높이를 0으로 하고 최대 높이를 배열의 마지막 요소로 정했다면

최소와 최대가 서로 교차되지 않을 때까지 반복을 진행한다.

 

자를 길이는 low와 high 합 / 2로 결정한다. 이유는 binary_search를 하기 위함이다.

배열 요소에 자를 길이를 뺀 결과가 0보다 큰 경우 sum에 뺀 결과를 누적한다.

sum이 가져갈 나무의 길이보다 큰 경우 현재 자를 길이를 저장하고, 최소 높이를 자를 길이의 + 1로 결정한다.

만약 작은 경우 최대 높이를 자를 길이의 - 1로 결정한다.

 

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

long long N,M;
int arr[1000001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>N>>M;

    for(int i = 0;i<N;i++)
        cin>>arr[i];

    sort(arr, arr + N);

    long long low = 0;
    long long high = arr[N - 1];
    long long answer = 0;

    while(low <= high){
        long long sum = 0;
        long long cnt = (low + high) / 2;

        for(int i = 0;i<N;i++){
            if(arr[i] - cnt > 0)
                sum += arr[i] - cnt;
        }
        if(sum >= M){
            answer = cnt;
            low = cnt + 1;
        }
        else{
            high = cnt - 1;
        }
    }
    cout<<answer<<'\n';
}