[백준/Java] 2805 - 나무 자르기

https://www.acmicpc.net/problem/2805

문제

 

---

풀이

주어진 나무 길이에서 M을 만족하는 길이를 계속 탐색해야 하기 때문에 이분 탐색으로 해결해야 겠다고 생각했다

절단기 높이의 최대와 최소를 찾으면서 그 중간값으로 비교를 한다

• 절단기 높이로 자른 나무 길이 총합이 M 보다 작으면 -> 절단기 높이를 너무 길게 잡은 것이므로 탐색 범위의 상한을 줄여줌
  • max = mid
• 절단기 높이로 자른 나무 길이 총합이 M 보다 크거나 같으면 -> 절단기 높이가 가능한 범위 내이지만 높이를 최대로 잡고 싶으므로 탐색 범위의 하한을 늘려줌
  • min = mid + 1

최종 출력은 Upper Bound 방식으로 찾았으므로, min을 출력하는데, min은 조건을 만족하는 가장 큰 값보다 1 큰 위치에서 멈추므로 -1 한 값을 출력해야 한다

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        // 나무 개수, 최소 가져가야 할 나무 길이 입력
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] tree = new int[N];

        // 나무 길이 입력
        // 최댓값도 같이 구해줌
        int max = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
            if (max < tree[i]) {
                max = tree[i];
            }
        }
        max++;

        int min = 0;
        int mid = 0;
        while (min < max) {
            // 현재 시도하는 절단기 길이
            mid = (min + max) / 2;

            long sum = 0;
            // 나무와 절단기 높이 차가 0 이상일 때만 더해줌
            for (int i = 0; i < N; i++) {
                int diff = tree[i] - mid;
                if (diff >= 0) {
                    sum += diff;
                }
            }

            /*
             * 자른 나무 길이 총합이 M 보다 작다면
             * 절단기 높이를 너무 길게 잡은 것이므로 max를 줄여줌
             */
            if (sum < M) {
                max = mid;
            }
            /*
             * 자른 나무 길이 총합이 M 보다 많거나 같다면
             * 절단기 높이를 너무 짧게 잡았거나 딱 맞는 것이므로 min을 늘려줌
             */
            else {
                min = mid + 1;
            }
        }

        // Upper Bound 방식으로 찾았으므로 -1
        // min은 조건을 만족하는 가장 큰 값보다 1 큰 위치에서 멈춤
        System.out.println(min - 1);

        br.close();
    }


}

결과