[BOJ] 2805. 나무 자르기

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

2805번: 나무 자르기

랜선 자르기 문제와 비슷하게 parametric search문제이다.

0부터 절단기의 최대길이가 될 수 있는 값(나무길이 중 가장 큰 값)까지를 이분 탐색을 진행하면서 필요한 나무만 가져갈 수 있는 절단기의 최대길이를 구한다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, m;
long long ans;
long long namu[1000000];
 
void solve(int left, int right) {
 
    long long h = (left + right) / 2;
    long long len = 0;
 
 
    //절단기 높이를 h(mid값)로 했을때 가져갈 수 있는 나무길이(len)을 구한다.
 //(각 나무에서 h만큼 자르고 남은 값을 더한다)
    for (int i = 0; i < n; i++) {
        if (namu[i] >= h) {
            len += (namu[i] - h);
        }
    }
 
    
    if (len > m) {
        if (left >= right) {
            //left가 right보다 같거나 커진 경우 이분탐색 중지하고 ans 값과 현재 h를 비교
            if (ans < h) ans = h;
            return;
        }
 
        //len이 가져가려는 길이m보다 크면 절단기 크기를 더 크게 해도 된다.
        solve(h + 1, right);
    }
    else if (len < m) {
        //len이 가져가려는 길이 m보다 작으면 절단기 크기h를 더 작게해야 한다.
        solve(left, h - 1);
    }
    else {
        //같은 경우에는 현재 절단기 크기와 비슷해서 최댓값을 저장
        if (ans < h) ans = h;
        return;
    }
 
 
}
 
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> namu[i];
    }
 
    //정렬
    sort(namu, namu + n);
 
    //left값은 0 right값은 나무 길이의 최대 값
    solve(0, namu[n - 1]);
 
 
    cout << ans << '\n';
 
    return 0;
}