[백준/JAVA] 2805

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());



        int[] trees = new int[N];

        int max = 0;
        int min = 0;

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());

            if (trees[i] > max) {
                max = trees[i];
            }
        }

        while (min < max) {
            int mid = (max + min) / 2;
            long sum = 0;

            for (int height : trees) {
                if ((height - mid) > 0) {
                    sum += height - mid;
                }
            }

            if (sum < M) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        bw.write(String.valueOf(min - 1));
        bw.flush();
    }
}

이분 탐색이 필요한 문제였다. 거기에 자료형 까지...?
아래는 시간 초과가 뜬 코드다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");

        int[] trees = new int[N];

        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        // 시작은 나무들 중에 가장 큰 값으로 시작한다.
        for (int i = Arrays.stream(trees).max().getAsInt(); i > 0; i--) {
            // 계속해서 나무를 잘랐을 때의 총 합을 초기화 한다.
            int sum = 0;
            // 나무의 개수만큼 반복한다.
            for (int tree : trees) {
                // 만약 나무가 자르려는 높이보다 크다면 잘라보고 그 높이를 합에 추가하고
                // 아니라면 그냥 넘어간다.
                if (tree > i) {
                    sum += (tree - i);
                } else continue;

                // 자르고 난 후의 나무의 높이가 원하는 길이를 얻었거나 더 얻었으면 루프 탈출
                if (sum >= M) {
                    bw.write(String.valueOf(i));
                    break;
                }
            }
            // 루프 탈출
            if (sum >= M) {
                break;
            }
        }
        bw.flush();
    }
}

솔직히 그냥 2중 반복문 써서 생각없이 짠 코드였는데....
역시나 시간 초과가 떠버렸다.
거기에 sum 값이 int 형이였는데 계속 틀렸다고 뜨길래
조건에 읽어보니 범위가 억 단위 이길래 자료형을 long 타입으로 변경하고
제출하니 해결되었다....
다음부터는 조건을 잘 읽고 생각하며 풀어야겠다.