[백준(Baekjoon)] 2805. 나무 자르기 (java, 이진탐색(binarySearch))

안녕하세요. 오늘은 백준의 2085. 나무 자르기 문제를 풀어보겠습니다.

---

1) 문제 링크

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

2) 문제 풀이

나무의 높이 M이 2,000,000,000으로 매우 크다. 따라서 이 문제는 이진탐색으로 풀어야 한다.

✔ 이진탐색문제: 뭘 탐색할 것인지?

그럼 뭘 탐색할건지 생각해봐야 한다. 문제에서 구하는 것은 "절단기에 설정할 수 있는 높이의 최댓값"이므로, 높이를 이진탐색하면 된다. trees배열을 입력받을 때 배열에 있는 나무 높이의 최댓값과 최솟값을 구한 후, 해당 범위 내에서 이진탐색을 수행하면 된다.

✔ while문 로직 순서

이진탐색 로직의 순서는 다음과 같다. 처음에 로직을 시작할 때, left는 주어진 나무 높이 중 최솟값, right는 주어진 나무 높이 중 최댓값을 나타낸다.

1. mid = (left + right) /2
2. mid값을 "절단기 높이"로 생각하고, 나무를 절단해본다. 절단해서 집으로 가져갈 수 있는 나무들의 총 합은 sum으로 나타낸다.
3. 만약 총 합 sum이 필요한 나무길이 M보다 작으면, 절단기 높이를 내려야 하므로, right을 mid - 1로 설정한다.
4. 만약 총 합 sum이 필요한 나무길이 M보다 크면, 절단기 높이를 더 올린다. left을 min + 1로 설정한다.
5. 해당 과정을 left값이 right값보다 커질때까지 반복한다.

3) 전체 코드

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

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 trees[] = new int[N];

        int left = 0;
        int right = Integer.MIN_VALUE;
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            trees[i] = num;
            right = Math.max(right, num);
            left = Math.min(left, num);
        }

        while (left <= right) {
            int mid = (left + right) / 2;
            long sum = 0;

            // 잘라진 나무 길이의 합
            for (int i = 0; i < N; i++) {
                if (trees[i] > mid) sum += trees[i] - mid;
            }

            if (M <= sum) left = mid + 1;
            else right = mid - 1;
        }

        System.out.println(right);
    }
}

4) 느낀점/ 틀린 이유

✔ 쓸데 없이 map을 사용했다

어제 보석쇼핑 문제를 풀면서 배운 map의 getOrDefault를 사용해보고 싶었나보다. 어려울 게 없는 문제였는데 스스로 문제를 꼬아 풀었다.

✔ right = mid - 1, left = mid + 1

나는 이진탐색 로직을 짤 때 left = mid - 1으로, right = mid + 1으로 대입했다. 조금만 생각해보면 틀린게 당연한데 너무 이상하게 풀었다.

아직은 이진탐색 문제를 풀 때 부족한 점이 많은 것 같다. 몇 문제 더 풀어봐야겠다.