[백준] 2805번 자바 나무자르기

문제 출처 

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

2805번: 나무 자르기

 

 

 

접근 방식 및 풀이

- 나무길이에 대한 높이를 계산할때 long타입 지정

- mid에서 +1해 가는 방식이 아니라 이분탐색을 통해 진행.

 

 

 

소스 코드 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i] = sc.nextInt();
        }

        int max = 0;
        Arrays.sort(arr);

        int left =1;
        int right =arr[n-1];
        long height =0;
        int mid =0;
        int ans=0;
        while(left <= right){

            height =0;
            mid =(left+right)/2;

            for (int i = 0; i <n ; i++) {
                if(arr[i]>=mid) {
                    height += (arr[i] -mid);
                }
            }
            
            if(height >= m){

                left = mid + 1;
            }else  if(height < m){
                right = mid-1;

            }




        }
        System.out.println(right);



    }
}

 

 

 

 

결과