나무 자르기

문제

나무 자르기

풀이

절단기의 높이를 로 설정했을 때 얻을 수 있는 나무의 길이를 라 합시다. 함숫값을 구하는 데 시간 복잡도는 이 듭니다. 이분 탐색의 upper bound를 이용하면 을 만족하지 않는 의 최솟값을 구할 수 있습니다. 여기서 을 빼면 해당 부등식을 만족하는 의 최댓값이 됩니다.

나무를 얻으려면 나무들의 높이의 최댓값보다는 작게 높이를 설정해야 합니다. 각 나무들의 높이를 로 나타내면 총 시간 복잡도는 가 됩니다.

코드

Python

n, m = map(int, input().split())
 
heights = list(map(int, input().split()))
 
 
def get_woods(cut_height: int) -> int:
    ret = 0
    for height in heights:
        ret += max(0, height - cut_height)
    return ret
 
 
lo = 0
hi = max(heights)
 
while lo < hi:
    mid = (lo + hi) // 2
 
    if get_woods(mid) >= m:
        lo = mid + 1
    else:
        hi = mid
 
print(lo - 1)

C++

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
vector<ll> heights;
 
ll getWoods(ll cutHeight) {
    ll ret = 0;
    for (ll height : heights)
        ret += max(0LL, height - cutHeight);
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
 
    ll lo = 0, hi = 0;
    heights = vector<ll>(n);
    for (int i = 0; i < n; i++) {
        cin >> heights[i];
        hi = max(hi, heights[i] + 1);
    }
 
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
 
        if (getWoods(mid) >= m)
            lo = mid + 1;
        else
            hi = mid;
    }
 
    cout << lo - 1;
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static long heights[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer tk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(tk.nextToken()),
            m = Integer.parseInt(tk.nextToken());
        
        long lo = 0, hi = 0;
        heights = new long[n];
        tk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            heights[i] = Long.parseLong(tk.nextToken());
            hi = Math.max(hi, heights[i] + 1);
        }
 
        while (lo < hi) {
            long mid = (lo + hi) / 2;
 
            if (getWoods(mid) >= m)
                lo = mid + 1;
            else
                hi = mid;
        }
 
        bw.write(lo - 1 + "");
        bw.close();
    }
 
    static long getWoods(long cutHeight) {
        long ret = 0;
        for (long height : heights)
            ret += Math.max(0, height - cutHeight);
        return ret;
    }
}