[Java] 백준 2805. 나무 자르기

정석·2024년 5월 10일

Java

알고리즘 학습

목록 보기

32/67

💡문제 분석 요약

이진탐색을 활용하여 여러 길이의 나무를 어떤 길이로 잘랐을 때 M 만큼의 남은 나무들의 합을 구할 수 있는지 푸는 문제.

💡알고리즘 설계

이진탐색을 위해
1. 나무 길이의 최대, 최소 값을 구함 그리고 해당 값으로 중간 값을 구해서 로직을 구현
2. 중간값을 통해 잘려진 남은 나무의 길이가 M보다 작다면, 보다 많이 잘라야 하기에 최대값을 중간값-1 로 조정
3. 반대의 경우 보다 덜 잘라야 하기에, 최소 값을 중간 값 + 1 로 조정

💡코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        int max = 0;
        int min = 0;
        for (int i = 0; i < N; i++) { // 나무의 길이들 배열에 저장
            arr[i] = Integer.parseInt(st.nextToken());
            if (max < arr[i]) {
                max = arr[i];
            }
        }

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

            for (int tree : arr) {
                // 자른 나무 길이 합 구하기
                if (tree - mid > 0) {
                    sum += tree - mid;
                }
            }
            // 자른 나무 길이의 합이 원하는 길이보다 적다면, 이진탐색에서 왼쪽 배열과 동일. 따라서 end 포인트를 mid - 1
            if (sum < M) {
                max = mid - 1;

            // 자른 나무 길이의 합이 원하는 길이보다 크다면, 이진탐색에서 오른쪽. 따라서 start 포인트를 mid + 1
            } else {
                min = mid + 1;
            }
        }
        System.out.println(min - 1);
    }
}

💡시간복잡도

O(NlogN)

💡 틀린 이유

아직 잘 모르겠으나, Upper Bound $ Lower Bound 의 개념과 관련된 거 같아 이 개념을 다시 확인해야 할 거 같다.

💡 틀린 부분 수정 or 다른 풀이

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        int max = 0;
        int min = 0;
        for (int i = 0; i < N; i++) { // 나무의 길이들 배열에 저장
            arr[i] = Integer.parseInt(st.nextToken());
            if (max < arr[i]) {
                max = arr[i];
            }
        }

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

            for (int tree : arr) {
                // 자른 나무 길이 합 구하기
                if (tree - mid > 0) {
                    sum += tree - mid;
                }
            }
            // 자른 나무 길이의 합이 원하는 길이보다 적다면, 이진탐색에서 왼쪽 배열과 동일. 따라서 end 포인트를 mid - 1
            if (sum < M) {
                max = mid - 1;

            // 자른 나무 길이의 합이 원하는 길이보다 크다면, 이진탐색에서 오른쪽. 따라서 start 포인트를 mid + 1
            } else if (sum > M) {
                min = mid + 1;
            }
            
            // 자른 나무 길이의 합이 원하는 값과 같아졌다면, 자른 위치인 mid를 출력
            else if (sum == M){
                System.out.println(mid);
                return;
            }
        }
    }
}