백준 2805 - 나무 자르기 (C++)

문제

해결 방법 : 정렬 후, 이분 탐색을 활용하여서 탐색한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //입력
    vector<long long> TreeVec;
    long long TreeNum, TreeLength, LengthMax=0;
    cin >> TreeNum >> TreeLength;
    for (long long i = 0; i < TreeNum; ++i)
    {
        long long a;
        cin >> a;
        TreeVec.emplace_back(a);
        if (LengthMax < a)
            LengthMax = a;
    }
    sort(TreeVec.begin(), TreeVec.end());
 
    //이분탐색
    long long Left = 0, Right = TreeVec.back(), Mid, Save;
    while (Left <= Right)
    {
        Mid = (Left + Right) / 2;
        
        long long CutLength = 0;
        for (long long j = TreeVec.size() - 1; j >= 0; --j)
        {
            if (TreeVec[j] > Mid)
                CutLength += TreeVec[j] - Mid;
            else
                break;
        }
 
        if (CutLength < TreeLength)
            Right = Mid - 1;
        else
        {
            Save = Mid;
            Left = Mid + 1;
        }
    }
    cout << Save;
}