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

[링크] : https://www.acmicpc.net/problem/2805

---

 

💎 문제 분석 & 제약 조건

 

 

문제 분석 :

 

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성

 

 

제약 조건 : 

 

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.

(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다.

나무의 높이의 합은 항상 M보다 크거나 같기 때문에,

상근이는 집에 필요한 나무를 항상 가져갈 수 있다.

높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

 

---

🚀 의사 결정

 

 

1. Scanner를 사용하여 상근이가 가져가려는 나무의 길이 M을 입력받고

 

2. 이분탐색의 시작점을 start , 이분 탐색의 종료점을 end로 정했을때, 반복문을 통해 나무 높이를 저장한 배열에서

 

3. 나무의 중간 높이 mid =  (start 값 + end값 ) / 2  로 계산하여, for문을 통해 , 입력받은 N개의 나무 수 만큼 반복했을 때,

 

절단기로 잘라서 가져 갈 수 있는 나무의 길이를 , trees 나무 배열의 i 번째 값을 mid 값과 비교 하여 더 큰 경우에 , 나무의 중간 높이 값을 뺀 차를 구하여 합산한 total 값을 구한다. 

 

3. 만약 , total 값이 상근이가 가져갈 나무의 길이 M값 보다 클 경우, 절단기 높이 최댓값을 갱신해서 result 에 할당하고, 더 높은 절단기 높이를 탐색하도록 mid + 1 하여 start 값으로 할당한다.

 

4. 상근이가 가져갈 나무의 길이가 부족한 경우 더 낮은 절단기 높이를 탐색하여 end 값으로 할당한다.

 

5. 최종적으로 while 조건문에서 이분 탐색의 시작점인 start 보다 이분 탐색의 종료점 end 값이 같거나 커지면,  상근이가 절단기에 설정할 수 있는 높이의 최댓 값이므로  result 값을 출력한다.

 

---

📜 소스코드(Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 나무의 수
        int M = sc.nextInt(); // 상근이가 집으로 가져가려는 나무의 길이
        int[] trees = new int[N]; // 나무 높이를 저장할 배열

        for (int i = 0; i < N; i++) {
            trees[i] = sc.nextInt();
        }

        long start = 0; // 이분 탐색의 시작점
        long end = 0; // 이분 탐색의 종료점
        for (int i = 0; i < N; i++) {
            if (trees[i] > end) {
                end = trees[i]; // 나무의 최대 높이로 설정
            }
        }

        long result = 0;
        while (start <= end) {
            long mid = (start + end) / 2; // 중간 높이 설정
            long total = 0;

            for (int i = 0; i < N; i++) {
                if (trees[i] > mid) {
                    total += trees[i] - mid; // 절단기로 잘라서 가져갈 수 있는 나무의 길이 계산
                }
            }

            if (total >= M) { // 가져갈 나무의 길이이 충분한 경우
                result = mid; // 절단기 높이 최댓값을 갱신
                start = mid + 1; // 더 높은 절단기 높이 탐색
            } else { // 가져갈 나무의 길이이 부족한 경우
                end = mid - 1; // 더 낮은 절단기 높이 탐색
            }
        }

        System.out.println(result); // 절단기에 설정할 수 있는 높이의 최댓값 출력
    }
}

---