백준 2805: 나무 자르기

문제

풀이

이분탐색을 위해 먼저 나무 높이들을 정렬해준다.
절단기 높이에 대한 이분탐색 진행 시작: 0 ~ 끝: 가장 높은 나무
mid1은 절단기의 높이
현재 절단기 높이의 lower bound 인덱스(e)를 찾아준다.
누적합 배열 sum에서 e~n-1까지 구간합을 구한 후 (절단기의 높이* e~n-1까지 나무 개수)를 빼준다.
이 값이 m 이상이면 답을 갱신해준다.
이후 이분탐색 종료까지 반복

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    static int n,m;
    static int trees[]; // 나무 배열

    public static void main(String args[]) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        trees=new int[n];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            trees[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(trees);
        long sum[]=new long[n];  // 누적합 배열
        sum[0]=trees[0];
        for(int i=1;i<n;i++){
            sum[i]+=trees[i]+sum[i-1];
        }

        int l=0,r=trees[n-1]; // 절단기 높이 이분탐색 시작 끝 구간
        int ans=0;
        while(l<=r){
            int mid1=(l+r)>>1;  // 절단기 높이

            int s=0,e=n-1;    //절단기 높이 lower bound 나무 이분탐색 구간
            while(s<e){
                int mid2=(s+e)>>1;
                if(trees[mid2]<mid1)s=mid2+1;
                else e=mid2;
            }					// e가 lower bound나무 인덱스
            long a=sum[n-1];		//a는 절단 후 가져갈 수 있는 나무
            if(e!=0)a-=sum[e-1];    // e ~ n-1 구간합
            a-=(long)mid1*(n-e);	// 절단기높이 * e~n-1까지 나무 개수
            if(a>=m){
                l=mid1+1;
                ans=Math.max(ans,mid1);
            }
            else r=mid1-1;
        }
        System.out.println(ans);
    }
}

#이분탐색 #이진탐색