🔍 Problem

2805번 나무 자르기

---

📃 Input&Output

---

🌁 문제 배경

가. 접근 방법
나무를 잘랐을 때, 자른 나무들의 합이 M보다 높은 경우에는 더 잘라야하고 낮은 경우에는 덜 잘라야한다.

나. 사용할 알고리즘 선택
이진 탐색

---

📒 해결 과정

가. 자른 나무들의 합이 M 보다 큰 경우
더 잘라야 하므로

left = mid + 1

나. 자른 나무들의 합이 M 보다 작은 경우
덜 잘라야 하므로

right = mid -1

다. 자른 나무들의 합이 M과 같은 경우
지금보다 나무를 더 잘랐을 때 (최대값을 구해야 하므로) 나무들의 합이 M보다 같을 수 있으므로,

left = mid + 1

---

💻 Code

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

public class P2805 {
    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 = new StringTokenizer(br.readLine());

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

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

        Arrays.sort(arr);

        int left, right, mid;
        long sum = 0;
        left = 0;
        right = arr[N - 1];
        mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;
            sum = 0;
            for (int i : arr) {
                if (mid < i) {
                    sum += i - mid;
                }
            }
            if (sum > M) {
                left = mid + 1;
            } else if (sum < M) {
                right = mid - 1;
            } else {
                left = mid + 1;    // 높이의 최대값을 구하기 위해 조금 더 높은 범위에서 찾아본다.
            }
        }
        bw.write(right + "\n");

        bw.flush();
        bw.close();


    }
}

🤔 느낀점

어렵다.