백준 2805번 - 나무 자르기 / Java

문제

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

2805번: 나무 자르기

이분 탐색을 활용하는 문제. 주어진 조건의 범위가 크므로 int가 아닌 long을 써줘야 한다.

 

 

알고리즘

1. 나무의 길이를 입력받으면서 나무길이의 최댓값을 max에 저장해놓는다

2. 1부터 max까지를 이분 탐색의 범위로 잡고 이분 탐색을 시작. 절단기의 높이에 관한 이분 탐색이며 이때 mid가 절단기의 높이이다

3. 절단기의 높이보다 높은 나무들을 잘라서 더해준다

4. 나무를 자른 합이 m보다 크거나 같을 경우 절단기의 높이를 저장한다

5. 절단기의 최대 높이를 출력한다

소스코드

/*
 * BOJ2805
 * 2020.02.04
 * Hyeonseong 
 */
import java.util.*;    
public class BOJ2805 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n; // 나무의 수
    long m; // 집으로 가져가려는 나무의 길이
    int wood[]; // 나무
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextLong();
        wood = new int[n];
        long max = -1;
        for(int i=0;i<n;i++) {
            wood[i] = scan.nextInt();
            if(max<wood[i]) {
                max = wood[i];
            }
        }
        long start = 1;
        long end = max;
        long maxCut = 0; // 절단기의 최대높이
        while(start<=end) {
            long mid = (start+end)/2; // 절단기의 높이
            long len = 0;
            for(int i=0;i<wood.length;i++) {
                if(wood[i]>=mid) {
                    len+=wood[i]-mid; // 가져갈 수 있는 나무의 총합
                }
            }
            if(len >= m) { // m보다 크거나 같다면
                if(maxCut < mid) { // 절단기의 최대높이를 저장한다
                    maxCut = mid; 
                }
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        System.out.println(maxCut);
    }
}