[백준 2805] 나무 자르기

in STUDY / PS

사용 알고리즘 : 이분 탐색

📚 문제

🔗 문제 링크

백준 2805번: 나무 자르기

📖 문제 설명

  • 나무 M미터가 필요함
  • 나무는 높이가 제각각
  • 절단기에 높이 H를 지정하면 H미터 위의 나무를 모두 절단
  • 적어도 M미터의 나무를 집에 가져가기 위한 절단기의 최대 높이 H를 구해야 함

🔍 입력 조건

  • 첫째 줄에 나무의 수 N과 필요한 나무의 길이 M이 주어짐 (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
  • 둘째 줄에 나무의 높이가 주어짐
  • 나무의 높이의 합은 항상 M보다 크거나 같음

🔍 출력 조건

  • 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력

🧩 문제 분류

  • 알고리즘: 이분 탐색
  • 자료구조: 배열
  • 난이도: Silver II

🚀 접근 방법

  1. 가능한 절단기 높이 범위를 설정 (0 ~ 나무 높이의 최댓값)
  2. 이분 탐색을 사용하여 최적의 높이를 찾음
  3. 각 높이로 잘랐을 때 얻을 수 있는 나무의 길이를 계산
  4. M미터 이상 얻을 수 있으면 높이를 늘리고, M미터 미만이면 높이를 줄임

💻 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2805 {
    private static final int MAX_HEIGHT = 1000000000;   // 문제에서 주어진 최대 높이
    static int N, M;
    static int[] trees;

    // 이분 탐색
    public static int cutTrees(int s, int e){
        int answer = 0;

        while (s <= e){
            int mid = (s + e) / 2;

            long sum = 0L;
            for (int i = 0; i < trees.length; i++){
                sum += Math.max(trees[i] - mid, 0);
            }

            if (sum < M) e = mid - 1;
            else {
                answer = mid;
                s = mid + 1;
            }
        }

        return answer;
    }

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

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

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

        System.out.println(cutTrees(1, MAX_HEIGHT));
    }
}

⏱ 시간 복잡도

  • O(N log(max(trees)))
    • 이분 탐색: O(log(max(trees)))
    • 각 단계에서 모든 나무 확인: O(N)

💾 공간 복잡도

  • O(N): 나무의 높이를 저장하는 배열의 크기

🧪 테스트 케이스

입력출력
4 7
20 15 10 17		15

📝 회고

  • 나무의 높이와 잘린 나무의 길이 합이 int 범위를 초과할 수 있음.
  • 1654 랜선 자르기 문제와 매우 유사하게 풀 수 있었다.

    📚 참고 자료

없음