백준 2805번 : 나무 자르기 [C++]

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

2805번: 나무 자르기

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int start, end, mid, N, M;
    int max = 0;
    vector<int> v;
    cin >> N >> M;

    for (int i = 0;i < N;i++)
    {
        int element;
        cin >> element;
        v.push_back(element);
    }

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

    start = 0;
    end = v[N - 1];

    while (start <= end)
    {
        long long int sum = 0;
        mid = (start + end) / 2;

        for (int i = 0;i < N;i++)
        {
            if (v[i] - mid > 0)
                sum += v[i] - mid;
        }

        if (sum >= M)
        {
            start = mid + 1;
            if(mid>max)
                max = mid;
        }

        else end = mid - 1;

    }

    cout << max;
}

마무리 : 입력의 조건을 보면 매우 큰 수로 입력을 한다는 것을 알 수 있다. 그래서 비교를 최소화하기 위해 이진 탐색으로 한다. 계속 비교를 하여 높이의 최대값을 출력해야하기 때문에 'else end = mid-1;' 에서 비교를하지 않는 이유이다.