[JAVA]백준 2805번: 나무 자르기

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

2805번: 나무 자르기

 

1. 문제 설명

 

상근이는 나무 M 미터가 필요해서 나무들을 잘라서 나무를 구할 것이다.

 

상근이가 절단기에 높이 H를 설정하면 톱날이 H미터 위로 올라가며 한 줄에 연속해 있는 나무들을 모두 절단한다.

 

상근이는 나무를 필요한 만큼만 집으로 가져가려고 할 때, 적어도 M 미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제.

 

2. 풀이

 

upper bound를 변형해서 풀 수 있는 문제이다.

 

집에 가져갈 수 있는 나무의 길이는 높이가 0일때부터 내림차순으로 정렬된 것과 같다.

 

따라서 적어도 M 미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값은 가장 처음 M 미터 보다 작은 나무를 가질 수 있는 높이의 -1이다.

 

높이의 합을 구하는 부분은 long으로 작성했다.

 

나무의 최대 개수가 1,000,000이고 최대 높이가 1,000,000,000 이기에 계산하는 부분에서 int의 범위를 초과할 수 있다.

 

*로직

- 이분탐색

- mid 높이 값으로 설정했을 때 가질 수 있는 나무의 길이가 M 보다 작은 경우 e=mid로 설정

- 나무의 길이가 M보다 크거나 같을 경우에는 s=mid+1로 설정

 

 

 

3. 코드

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

public class Main {

    public static int tree_num;
    public static long need_tree;
    public static int[] tree;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());


        // 입력
        tree_num = Integer.parseInt(st.nextToken());
        need_tree = Long.parseLong(st.nextToken());

        tree = new int[tree_num];

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < tree_num; x++) {
            tree[x] = Integer.parseInt(st.nextToken());
        }


        System.out.println(binarySearch());

    }

    public static int binarySearch() {
        int s = 0;
        int e = 1000000000;

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

            long sum = 0;

            for (int x : tree) {
                if (x > mid) {
                    sum += x - mid;
                }
            }

            if (sum >= need_tree) {
                s = mid + 1;
            } else {
                e = mid;
            }
        }

        return e - 1;
    }
}