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

문제

나무 자르기

정답

import java.util.*;

class Main {
  static int n; // 나무의 수
  static int m; // 가져 가려는 길이
  static int[] arr;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    m = sc.nextInt();

    arr = new int[n];

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

    Arrays.sort(arr);

    int left = 0;
    int right = arr[arr.length - 1];
    int answer = 0;

    while(left <= right) {
      int mid = (left + right) / 2;
      long sum = 0;

      for(int i = 0; i < arr.length; i++) {
        if(arr[i] > mid) sum += arr[i] - mid;
      }

      if(sum >= m) {
        answer = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    System.out.println(answer);
  }
}

• 이분 탐색을 이용해서 푸는 문제입니다.
• 이분 탐색을 구현하는데 약간 어려움을 겪었습니다.
• sum이 9자리를 넘을 수 있기 때문에 long을 사용합니다.