[BOJ] 2805번 나무 자르기 - JAVA(자바)

2805번: 나무 자르기

💡 이진탐색(Binary Search) 

 

이진탐색으로 해결할 수 있는 문제들의 유형은 비슷하다. lt와 rt를 정하고 lt ~ rt 사이에 찾고싶은 답이 분명히 있다라는 확신이 있는 문제에 적용한다 + 최대/최소

---

구하고자 하는 것 : 절단기를 설정할 수 있는 높이의 최대값

lt = 0 : 절단기에 설정할 수 있는 가장 작은 값
rt : 나무의 길이 중 가장 긴 값
➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다.

 

mid = (lt + rt) / 2

 

절단기의 길이가 mid이면 답으로써 가능한 숫자인가 검증 ➜ 얻어갈 수 있는 나무 길이를 구하는 함수 생성

• 얻어갈 수 있는 나무의 길이가 필요한 나무의 길이보다 길면 절단기를 더 늘려도 됨 lt=mid+1
• 반대이면 절단기 길이를 더 줄이기 rt=mid-1

 

👨🏻‍💻 실행코드

import java.util.Arrays;
import java.util.Scanner;

class Main {

    public long count(int[] arr, int h) {
        long sum = 0; // 얻어갈 수 있는 나무 길이

        for (int i = 0; i < arr.length; i++) {
            int x = arr[i] - h;
            if(x>0)
                sum += x;
        }
        return sum;
    }

    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        int lt = 1;
        int rt = Arrays.stream(arr).max().getAsInt();

        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if(count(arr, mid) == m) {
                answer = mid;
                break;
            }
            if (count(arr, mid) > m) { // 필요한 나무길이 m보다 길거나 같은 나무를 구했다면
                answer = mid;
                lt = mid + 1; // 높이의 최대값을 구하기 위해 절단기 높이를 더 높여보기
            } else rt = mid - 1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner s = new Scanner(System.in);

        int n = s.nextInt(); // 나무의 수
        int m = s.nextInt();  // 필요한 나무 길이

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) { // 각 나무의 길이
            arr[i] = s.nextInt();
        }
        System.out.println(T.solution(n, m, arr));
    }
}

 

🛠️ 1트 실패 : 집으로 가져가려하는 나무의 범위는 (1,000,000 ≤ M ≤ 2,000,000,000 ) 따라서 얻을 수 있는 나무 길이의 합인sum의 변수형이 int가 아닌long 으로 선언해주어야 한다.

---

[JAVA/알고리즘] 이진 탐색 알고리즘을 이용한 문제해결