백준 #2805 나무 자르기


BOJ #2805 - 나무 자르기

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

# 문제 분류

이분 탐색

풀이 접근 방법


이분 탐색의 원리를 제대로 파악하지 못하면 풀기 힘든 문제. 1 3 5에서 4를 찾으려고 할 때 lo<=hi로 만들어진 이분 탐색의 경우에는 lo가 5를 가리킨 후에 이분 탐색이 종료되게 된다. 그러나 이 문제의 경우에서는 최소한 M개 만큼의 나무는 챙겨가야하므로, 똑같은 방식으로 이분 탐색을 돌린다면 M개 보다 적은 나무를 챙겨가게 된다. 따라서 만약 lo로 설정했을 때 잘리는 나무의 수가 같은 경우에는 그대로 챙겨가고, 그것이 아닌 경우에는 위에서 말한 이분 탐색의 특성이 적용된 것이므로 -1을 하여 원래 자리를 찾아가도록 한다.


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, height;

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

    cin >> N >> M;
    vi tree;

    for (int i = 0; i < N; i++) {
        cin >> height;
        tree.emplace_back(height);
    }

    int l = 0, h = 1'000'000'000;

    // binary search
    while (l <= h) {
        int m = l + h >> 1;

        ll sum = 0;
        for (int p : tree) {
            if (p > m)
                sum += p - m;
        }

        if (sum >= M) {
            l = m + 1;
        } else
            h = m - 1;
    }

    cout << l - 1;
}