2805번

2805번 - 나무 자르기

이분 탐색 문제 중 하나, 앞에서 풀어봤던 1654번이랑 거의 똑같다.

이 문제도 N을 제외한 모든 자료형에 int 대신 long long을 써야했다.

자꾸 습관적으로 main 에서 long long 쓰지만 함수에서 int를 써버리는 실수를....

이분 탐색에 대해서 궁금증

-  이분 탐색을 하다보면 결국 low, mid , high 가 거의 근사한 값에 다가 올 텐데.. int 형 변수로 하면 low 랑 high랑 1차이가 나게된다..

   항상 답을 low로 출력해야하는지.. mid 로 출력해야하는지.. 

   내일 궁금증을 어디에 올려서라도 해결해야 겠다..

  

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool overM(const vector<long long> &tree, long long mid, long long M)
{
    long long ans = 0;
 
    for (int i = 0; i < tree.size(); i++)
    {
        int canGet = tree[i] - mid;
        if (canGet >= 0)
        {
            ans += canGet;
        }
    }
 
    return ans >= M;
}
int main()
{
    int N;
    long long M;
    vector<long long> tree;
    cin >> N >> M;
 
    for (int i = 0; i < N; i++)
    {
        long long height;
        cin >> height;
        tree.push_back(height);
    }
 
    sort(tree.begin(), tree.end());
 
    long long low = -1;
    long long high = tree.back()+1;
    long long mid;
 
    for (int it = 0; it < 100; it++)
    {
        mid = (low + high) / 2;
 
        if (overM(tree, mid, M))
        {
            low = mid;
        }
        else
        {
            high = mid;
        }
    }
 
    cout << low << endl;
 
 
    return 0;
}