[백준 2805] 알고리즘 56일차 : 나무 자르기

www.acmicpc.net/problem/2805

2805번: 나무 자르기

이분탐색 C++

오늘도 이분탐색으로 최댓값을 구하는 스킬을 사용하는 문제

그래서 저번 랜선자르기 코드 거의 그대로 씀

 

접근방법

H의 길이를 0부터 가장 높은 나무길이 범위내에서 이분탐색하여 최댓값을 구한다.

 

오답노트

자른 나무의 길이 합과 M이랑 비교하는 함수에서

합 계산할때 음수도 같이 더하는걸로 해버려서 오류났었다.

양수일때만 더하는걸로 고치고 통과

 

소스코드

#include <iostream>
using namespace std;
long long height[1000000];
int N;
long long M;

bool isEnough(long long H){
    long long total = 0;
    for(long long i = 0 ; i < N ; i++)
        total += (height[i]-H > 0 ? height[i]-H : 0);
    return total>=M ? true : false;
}
long long binarySearchMax(long long s, long long e){
    long long mid = 0;
    while(s <= e){
        mid = (s+e)/2;
        if(isEnough(mid)){
            s = mid+1;
        }else{
            e = mid-1;
        }
    }
    return s-1;
}
int main(){
    cin >> N >> M;
    long long max = 0;
    for(int i = 0 ; i < N ; i++){
        cin >> height[i];
        max = ( max <= height[i] ? height[i] : max );
    }
    cout << binarySearchMax(0,max);
    
    return 0;
}