백준 2805 나무 자르기(Java)

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

2805번: 나무 자르기

---

 

해석 및 팁

 

---

 

이 문제는 이분 탐색을 활용하는 문제입니다. 다만 주의할 점은 나무를 자를 때 자르는 위치가 주어진 나무의 높이보다 클 경우 음수가 나오기 때문에 나무의 높이가 자르는 위치보다 높을 때만 더해야 합니다.

 

---

 

Java 코드

 

---

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

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();
    Arrays.sort(arr);
    int l = 0;
    int r = arr[n-1];
    
    while(l <= r) {
      long sum = 0;
      int mid = (l + r) / 2;
      for(int i = 0; i < n; i++) {
        if(arr[i] > mid) sum += (arr[i] - mid);
      }
      if(sum < m) r = mid - 1;
      else l = mid + 1;
    }
      
    System.out.println(r);
  }
}