2805번: 나무 자르기(20분)

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

구현 아이디어 5분 구현 15분

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); 

    long N{}, M{};
    cin >> N >> M;

    vector<int> Forest(N);

    for (long i = 0; i < N; ++i)
    {
        cin >> Forest[i];
    }

    sort(Forest.begin(), Forest.end());

    int LeftHeight{}, RightHeight{}, MiddleHeight{};
    LeftHeight = 0;
    RightHeight = Forest.back();
    MiddleHeight = (LeftHeight + RightHeight) / 2;

    while (LeftHeight <= RightHeight)
    {
        long Sum{};

        for (long i = N - 1; i >= 0; --i)
        {
            Sum += long((Forest[i] - MiddleHeight > 0 ? Forest[i] - MiddleHeight : 0));

            // 연산을 줄이려고...
            if (Forest[i] - MiddleHeight <= 0)
            {
                break;
            }
            if (Sum > M)
            {
                break;
            }
        }

        if (Sum < M)
        {
            RightHeight = MiddleHeight - 1;
        }
        else if (Sum == M)
        {
            cout << MiddleHeight;
            return 0;
        }
        else
        {
            LeftHeight = MiddleHeight + 1;
        }

        MiddleHeight = (LeftHeight + RightHeight) / 2;
    }

    cout << MiddleHeight;

    return 0;
}