greentea31's Note

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

풀이 과정

절단기 높이 H보다 높은 나무의 길이를 길이 - H 만큼 잘라서 길이 M만큼 챙겨야 할 때, 가능한 최소 절단기의 높이를 구하는 문제이다.

나무 최대 길이 = 절단기 높이를 초기값으로 잡고, 길이 M만큼 챙길 수 있을 때 까지 절단기 높이 H를 1씩 낮추는 방법이 먼저 떠오르지만, 나무 길이가 10억까지 들어오므로 100% TLE가 날 것이다. 따라서 이분 탐색을 활용하여 문제를 해결하였다.

소스 코드

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

bool cut(long long mid, vector<long long>& vec, int N, int M) {
    long long sum = 0;

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

        if (sum >= M) {
            return true;
        }
    }

    return false;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<long long> tree(N);

    for (int i = 0; i < tree.size(); i++) {
        cin >> tree[i];
    }

    long long left = 0;
    long long right = *max_element(tree.begin(), tree.end());
    long long mid;
    long long answer;

    while (left <= right) {
        mid = (left + right) / 2;
        if (cut(mid, tree, N, M)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << answer;

    return 0;
}