[실버 2] [Java] 백준 2805번: 나무 자르기

아이디어

이진 탐색 문제이다.

나무의 개수 N, 필요한 나무의 길이 M을 입력받고

N개의 나무의 길이를 입력받아 배열로 저장한다.

그 중 가장 긴 나무의 길이를 탐색할 높이 H의 최대값으로 설정한다.

 

정석적인 이진 탐색 알고리즘과 같이, 초기 중앙값으로 H를 설정하여 나무를 잘랐을 때

자른 나무의 길이의 합인 sum이 M 이상이면 중앙값을 정답에 저장한다.

그 후 sum이 M보다 큰 경우 sum을 줄여야 하므로 H를 높여아하니 left를 mid + 1로 설정한다.

 

다시 mid를 구한 후 sum이 M 이상인지 아닌지 확인한 후

M 미만이라면 right를 mid - 1로 설정한다.

이 과정을 right가 left 이하가 되기 전까지 반복한다.

 

이를 코드로 구현하면 다음과 같다.

import java.io.*;

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

        String[] input  = br.readLine().split(" ");
        int N  = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int[] trees = new int[N];
        int max = 0;

        input  = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(input[i]);
            if (trees[i] > max) {
                max = trees[i];
            }
        }

        int left = 0, ans = 0, right = max;
        while (left <= right) {
            int mid = (left + right) / 2;
            long sum = 0;
            for (int tree : trees) {
                if (tree > mid) {
                    sum += tree - mid;
                    if (sum >= M) {
                        break;
                    }
                }
            }
            if (sum >= M) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        bw.write(ans+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.