[ BOJ 백준 2805번 - 나무 자르기 ] 해설 및 코드

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

 

목적

절단기에 설정한 높이 h 이상의 나무만 잘라 그 합이 m이상이 되도록 하는 h를 구하자.

 

접근법

1. 절단기의 높이를 1씩 늘리거나 줄여서 찾기에는 높이의 범위가 너무 크므로, 이분 탐색 알고리즘으로 접근한다. 

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int n,m,a[1000001],ret;
void bs(int l,int r){
    if(l>r){
        ret=r;
        return;
    }
    
    int h=(l+r)/2;
    
    long long k=0;
    for(int i=n-1;i>=0;--i){
        k+=(a[i]-h);
        if(k>=m)break;
    }
    
    if(k>=m) bs(h+1,r);
    else bs(l,h-1);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    for(int i=0;i<n;++i)cin>>a[i];
    sort(a,a+n);
    bs(0,a[n-1]);
    cout<<ret;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.