[백준 2805] 나무 자르기 (JAVA)

백준 2805번 문제 - 나무 자르기

2805번: 나무 자르기

---

문제 분석 

 

 

• 상근이는 나무 M미터가 필요하다.
• 목재절단기는 상근이는 절단기에 높이 H를 지정하면 H보다 큰 나무는 윗부분이 잘린다.
  • 20, 15, 10 17 나무가 있다고 할 때 H가 15이면, 5+0+0+2 = 7
  • 7M가 잘린다.
• 나무를 필요한 만큼만 집으로 가져가려고 한다.
• 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

---

해결 포인트

 

• 이진 탐색
• mid 값보다 트리의 높이가 클 경우, 트리의 높이 - mid 값들을 더해 합을 구한다.
  • 합이 M을 넘지 않을 경우, end = mid
  • 합이 M을 넘을 경우, start = mid + 1
•  

---

코드

 

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

public class Main {
    public static ArrayList<Long> trees;
    public static long M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        M = Long.parseLong(st.nextToken());

        trees = new ArrayList<>();
        long max = 0;
        st = new StringTokenizer(br.readLine());
        for (long i = 0; i < N; i++) {
            long num = Long.parseLong(st.nextToken());
            trees.add(num);
            max = Math.max(max, num);
        }

        bw.write(getTreeSize(1, max) + "\n");
        bw.flush();
        bw.close();
    }

    public static long getTreeSize(long start, long end) {
        if(start >= end) {
            return start - 1;
        }
        long mid = (end+start)/2;
        long sum = 0;
        for (int i = 0; i < trees.size(); i++) {
            if (mid < trees.get(i)) {
                sum += trees.get(i) - mid;
            }

        }

        if(sum < M) {
            return getTreeSize(start, mid);
        }
        else {
            return getTreeSize(mid+1, end);
        }
    }
}