BOJ 2805 나무 자르기

1 개요

BOJ 2805 나무 자르기

• 백준 온라인 저지 2805번 문제
• BOJ 27단계

2 C++

#include <iostream>
using namespace std;

int N, M;
int A[1000001];

long getTree(int height) {
    long sum = 0;
    int len;
    for(int i=1; i<=N; i++) {
        len = A[i] - height;
        if(len > 0) {
            sum += len;
        }
    }
    return sum;
}

long solve(int end) {
    int start = 1;
    long answer = 0;
    while(start <= end) {
        int mid = (start + end)/2;
        if(getTree(mid) >= M) {
            start = mid + 1;
            if(mid > answer) {
                answer = mid;
            }
            continue;
        }
        end = mid - 1;
    }
    return answer;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    int max = 0;
    for(int i=1; i<=N; i++) {
        cin >> A[i];
        if(A[i] > max) max = A[i];
    }
    cout << solve(max);
}