📝문제

이 문제를 풀 때 간과하고 넘어간 것이 많아서 그 부분들을 바로잡느라 좀 힘들었다..
내가 간과한 것

1. 나무 하나 높이의 범위와 m(구하려는 값)의 범위가 int라고 long 타입을 쓰지 않은 것
   • 최악의 경우 높이가 1,000,000,000인 나무가 1,000,000개 있는 것이고 그 값을 다 더해야할 수도 있는데 그런 경우를 생각하지 못했다.

2. 이분탐색을 고려하지 않은 것
   • 처음 문제를 풀 때는 이분탐색을 생각하지 않고, 절단기의 초기 높이를 가장 높은 나무의 높이에서 구하려는 값을 뺀 결과로 설정했다. 그리고나서 그 값으로부터 1씩 더해가면서 계산과정을 반복했는데 그렇게하면 시간초과가 발생했다. 조금이라도 계산과정을 줄여야했고, 그래서 이분탐색으로 로직 방향을 바꿔서 풀었다.

📌코드

package Baekjoon;

import java.util.*;
import java.io.*;

public class BOJ2805 {

  static int n;
  static int m;
  static long[] trees;
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    trees = new long[n];
    long maxH = 0;//나무 높이
    st = new StringTokenizer(br.readLine());
    for(int i = 0;i < n; i++){
      trees[i] = Integer.parseInt(st.nextToken());
      maxH = Math.max(trees[i], maxH);//최대 나무 높이
    }
    // 구하려는 절단된 나무들의 길이가 가장 높은 나무의 높이보다 클 수도 있다.
    // 절단기 높이 유효 범위
    long start = 1;
    long end = maxH;
    long answer = 0;
    while(start <= end){
      long mid = (start + end) / 2;//현재 절단기 높이
      long result = 0;
      for(int i = 0; i < n; i++){
        if(trees[i] > mid) result += (trees[i] - mid);
      }
      if(result >= m){
        start = mid+1;
        answer = Math.max(answer, mid);
      }
      else{
        end = mid-1;
      }
    }
    System.out.println(answer);
  }
}