2805번 : 나무 자르기

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

2805번: 나무 자르기

 

 

문제

 

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc. nextInt(); sc.nextLine();

        int arr[] = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = sc.nextInt();
        }

        int start=0;
        int end=Arrays.stream(arr).max().getAsInt();
        int cnt=0;

        //이진 탐색 수행
        while(start<=end) {
            int h = (start+end)/2;
            long sum=0; //잘라진 나무 높이
            for(int i : arr) {
                //잘랐을 때의 나무의 높이 계산
                if(i>h) sum+=(i-h);
            }
            if(sum<m) end=h-1; //나무의 높이가 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
            else { //나무의 높이가 충분한 경우 덜 자르기(오른쪽 부분 탐색)
                cnt=h; //최대한 덜 잘랐을 때가 정답이므로, cnt에 계속 기록한다.
                start=h+1;
            }
        }
        System.out.println(cnt);
    }
}

 

 

해결방법

잘라진 나무의 길이를 기준으로 이진 탐색을 수행하여 문제를 해결하였다.

처음에 속도를 빠르게 하고자 입력받은 나무의 길이가 담긴 배열을 내림차순 정렬하여 풀었는데 시간초과가 났다.

정렬이 은근 느린 것 같다.(이 점은 더 알아봐야 함) 

그리고 잘랐을 때의 나무의 높이가 int형의 최댓값인 약 21억을 넘을 수 있으므로 long형으로 선언해줘야 한다.