[백준 BOJ][C++]2805번 나무 자르기 풀이: 이진 탐색

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

풀이

---

이 문제는 이진 탐색 알고리즘을 사용하여 해결할 수 있습니다.

1. 시작 수 s = 0, e = 배열의 가장 큰 원소의 값으로 지정
2. mid = (s+e)/2 는 절단기의 높이, sum = 절단기의 높이 보다 큰 나무에 대해 잘린 나무의 길이의 총합 계산
3. sum과 가져가려고 하는 나무의 길이 m 비교
   • sum과 m이 같다면 현재 mid가 절단기의 높이의 최댓값이므로 break
   • sum이 m보다 크다면 절단기의 높이 ans를 갱신, s = mid + 1
   • sum이 m보다 작다면 e = mid -1
4. s <= e 일 때까지 2~3 과정 반복

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

int n, m;
vector<int> tree;
int ans;

int main(void) {

    int s = 0;
    int e = 0;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        tree.push_back(x);

        if (e < x)
            e = x;
    }

    while (s <= e) {
        int mid = (s + e) / 2;
        long long sum = 0;

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

        if (sum == m) {
            ans = mid;
            break;
        }
        else if (sum > m) {
            ans = max(ans, mid);
            s = mid + 1;
        }
        else {
            e = mid - 1;
        }
    }

    cout << ans;

    return 0;
}