백준 2805 / C++

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

2805번: 나무 자르기

 

이분탐색(파라매트릭 서치) 입문문제이다. 

설명은 코드로 대체.

 

[ 코드 ] 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, h[1000001];
 
// 높이 x로 자른 나무들의 합이 m이상인지 판별하는 함수
int check(ll x) {
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        sum += max(1LL * 0, h[i] - x);
    }
    return sum >= m;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> h[i];
    ll l = 0, r = 1e9, ans = -1;
    // 높이를 이분탐색 
    // 높이의 최댓값을 구하므로.. 
    while (l <= r) {
        ll mid = (l + r) / 2;
        // 높이 mid가 가능하다면 하한을 키워줌 
        if (check(mid)) {
            l = mid + 1;
            ans = mid;
        }
        // mid가 불가능하면 상한을 줄여줌 
        else r = mid - 1;
    }
    cout << ans << '\n';
}