[백준/이분탐색/C++] 2805번 나무 자르기

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

2805번: 나무 자르기

유의사항

• 자른 길이의 합을 구할때 나무가 자르는 길이보다 큰 경우에만 수행이 되도록 조건을 넣어주어야 한다
• 자른 길이와 길이의 합은 long long int 형으로 선언해주어야 한다

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    int start = 0;
    int end = 0;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        if(x>end) end = x;
        v.push_back(x);
    }

    long long int mid = 0; // 자르는 길이
    long long int total = 0; // 자른 길이 합
    int result = 0; // 높이의 최대값

    while(start<=end){
        total = 0;
        mid = (start + end)/2;

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

        if(total<m) end = mid - 1; // 자른 길이의 합이 필요한 것보다 작은 경우
        else {
            result = mid;
            start = mid + 1;
        }
    }
    cout << result << '\n';

    return 0;
}