백준 2805번 나무자르기

백준 2805번 나무자르기

#include <iostream>
#include <queue>
#include<stack>
#include <cmath>
#include<string>
#include<vector>
#include<algorithm>
#include <cstring> //memset
using namespace std;
 
int n;
long long m;
long long Max = 2000000000;
long long Min = 1;
 
long long tree[1000001];
 
 
long long Cut_Tree(int mid) {
    long long ret = 0;
    for (int i = 1; i <= n; i++) {
        long long ans = tree[i] - mid;
        if (ans > 0) {
            ret += ans;
        }
    }
    return ret;
}
 
 
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
 
 
    for (int i = 1; i <=n; i++)
        cin >> tree[i];
 
    long long high = Max;
    long long low = Min;
    long long mid;
    long long ans=0;
    while (low <=high) {
        mid = (low + high) / 2;
        long long ret = Cut_Tree(mid);
        if (ret >= m) {
            ans = max(ans, mid);
            low = mid+1;
        }
        else {
            high = mid - 1;
        }
    }
    cout << ans << endl;
 
    return 0;
}

문제 출처:https://www.acmicpc.net/problem/2805

이분 탐색 문제였습니다. 

long long이 아니라 int형으로 풀고있으니 당연히 오답이 뜨는것을...