boj 2805 나무 자르기

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

2805번: 나무 자르기

잘려진 나무의 길이를 적어도 M으로 하기위한 높이의 최댓값을 구하는 문제입니다.

최적의 값을 구하는 문제이기때문에 이분탐색 중에서 파라매트릭 서치를 이용하여 해결할 수 있습니다.

 

높이를 1~list중 최대로 설정하여 파라매트릭 서치를 돌리고

잘려진 나무의 높이의 합이 M보다 작으면 l ~ m-1

잘려진 나무의 높이의 합이 M보다 크거나 같으면 m+1~r

로 높이를 재설정하여 구하면 됩니다.

 

최적의 값을 구해야하기 때문에 합이 M이라고 해서 바로 리턴해버리는 실수가 없어야합니다.

(합이 M이 나오지 않는 입력도 주어질 수 있습니다.)

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[];
    static int N, M, maxheight;
    static long ans = 0;
 
    static void binarysearch(long l, long r) {
        if (l > r)
            return;
 
        long m = (l + r) / 2;
        long sum = 0;
        for (int i = 1; i <= N; i++) {
            if (list[i] <= m)
                continue;
            sum += (list[i] - m);
        }
 
        if (sum >= M) {
            ans = Math.max(ans, m);
            binarysearch(m + 1, r);
        } else {
            binarysearch(l, m - 1);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            maxheight = Math.max(maxheight, list[i]);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        binarysearch(1, maxheight);
        System.out.println(ans);
    }
}