[백준/C++] 2805번 나무 자르기

문제: www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

문제풀이

 

이분 탐색 문제 중에서도 조건을 만족하는 값들 중 최댓값을 구하는 문제이다.

 

(나무길이) - (벌목기 높이)의 총합 >= M

을 만족하는 벌목기 높이의 최댓값을 구해야 한다.

 

최댓값을 구하기 위해서 위의 조건을 만족하더라도 루프를 멈추지 않고 계속 탐색한다.

 

 

코드

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    long long N,M;
    cin>>N>>M;

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

    /*
    long long 형의 데이터 범위는 문제의 조건보다 한참 크지만
    문제에서 요구하는 메모리 제한(256MB) 또한 충분하기 때문에
    long long 형으로 선언하는게 마음이 편한 것 같습니다.
    */

    long long start=0;
    long long end=2000000000;
    long long mid;
    long long max;
    while(start<=end){
        mid = (start+end)/2;
        
        long long sum=0;
        for(int i=0; i<N; i++){
            if(tree[i]-mid > 0)
                sum += (tree[i]-mid); //자른 나무길이 총합
        }

        if(sum>=M){
            max = mid;
            start = mid+1; //벌목기 높이의 최대값을 구하기 위해 계속 탐색
        }
        else{
            end = mid-1;
        }
    }
    
    cout<<max; //결과 출력
    
    return 0;
}

 

결과

 

alalgorithm 라이브러리의 upper_bound() 함수를 사용하는 방법도 있지만 이분 탐색을 공부할 겸 코드로 구현해보았습니다.