[BOJ 2805] 나무 자르기

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

풀이

• 이분탐색을 통해 mid를 기준으로 왼쪽, 오른쪽 구간에서 크기를 비교하여 mid를 재설정하며 정답을 구한다.

코드(C++)

#include<bits/stdc++.h>
using namespace std;

long long int n, m;

int main() {
    scanf("%lld %lld", &n, &m);
    
    long long int maxN = 0;
    long long int tree[n + 1];
    
    for(int i = 0; i < n; i++) {
        scanf("%lld", &tree[i]);
        
        if(tree[i] > maxN) {
            maxN = tree[i];
        }
    }
    
    long long int left = 0;
    long long int right = maxN;
    long long int ans = 0;
    
    while(left <= right) {
        long long int mid = (left + right) / 2;
        long long int total = 0;
        
        for(int i = 0; i < n; i++) {
            if(tree[i] > mid) {
                total += tree[i] - mid;
            }
        }
        
        // 나무가 남으면, 자르는 높이를 크게 설정
        if(total >= m) {
            ans = mid;
            left = mid + 1;
        }
        
        else {
            right = mid - 1;
        }
    }
    
    printf("%lld", ans);
}