백준 2805 나무자르기 - 이분탐색 C++ (미완)

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

불러오는 중입니다...

이 문제도 이분탐색을 물어보는 문제였다.

랜선자르기 문제(1654번)과 거의 동일한 구조이다.

#include <iostream>
using namespace std;
 
int N;
long long meter_of_tree;
long long tree[1000001];
 
bool ispossible(int height){
    long long count=0;
    for(int i=0; i<N; i++){
        if(tree[i]>height)
            count+=tree[i]-height;
    }
 
    if(count>=meter_of_tree)
        return true;
    else
        return false;
}
 
int main(void){
    cin>>N>>meter_of_tree;
    long long high=0;
    for(int i=0; i<N; i++) {
        cin >> tree[i];
        if(high<tree[i])
            high=tree[i];
    }
    long long low=1;
    long long result_height=0;
    while(low<=high){
//        cout<<high<<" "<<low<<"\n";
        long long mid= (high+low)/2;
//        cout<<"mid is "<<mid<<"\n";
        if(ispossible(mid)){
            if (result_height<mid)
                result_height = mid;
            low=mid+1;
        }
        else{
            high = mid-1;
        }
    }
    cout<<result_height;
 
}

이문제를 맞추기 전에 한번 틀렸었는데, 

31번째 줄에 while(low<=high) 를 while(low<high)로쓴

것 뿐이었는데 틀렸다고 결과가 떴다. *코드길이가 1B밖에 차이안남.

 

그 이유를 봤었는데 (ac받은 코드들 참조하면서)

 

결국 지금 mid 값보다 무조건 크거나 작은 값을 참조해야 하는건 맞는거고,

low=high의 순간은 결국 low=mid=high 가 되는 것과 마찬가지가 되기 때문에.

(사실 low<high라고 할 경우엔 어떤 차이점이 생기는지 잘 떠오르지 않는다..)

이건 기회되면 더 알아보도록 하자.