백준 2805번 나무 자르기 (JAVA)

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

2805번: 나무 자르기

 

저는 for문과 이분 탐색을 통해 문제를 풀었습니다.

for문으로는 0부터 최고값까지 해보면서 합이 M보다 큰지를 판단하여 크다면 결과값을 초기화하여 문제를 풀었습니다.

이때 시간복잡도는 n*최고값이기 때문에 1초 이내로 동작하기 힘듭니다.

이분탐색의 경우, 합이 M보다 큰지를 판단하여 크다면 start값을 작다면 end값을 변경하면서 가장 큰 값을 찾았습니다.

시간복잡도가 n*log(최고값)이기에 1초내에 동작할 수 있어 이를 통해 문제를 해결하였습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Test {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int targetSum = Integer.parseInt(st.nextToken());
        int[] treeHeight = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i++){
            treeHeight[i] = Integer.parseInt(st.nextToken());
        }
//        int result = cal(treeHeight,n,targetSum);
        int result = calBinarySearch(treeHeight,n,targetSum);
        System.out.println(result);
    }
    private static final int MAX = 1_000_000_000;
    private static int cal(int[] treeHeight, int n, int targetSum) {
        int result = 0;
        for(int i = 0 ; i <= MAX  ; i++){
            if(check(i,treeHeight,n,targetSum)){
                result = Math.max(result,i);
            }
        }
        return result;
    }
    private static int calBinarySearch(int[] treeHeight,int n , int targetSum){
        int result = 0;
        int start = 0;
        int end = MAX;
        while(start <= end){
            int mid = (start+end)/2;
            if(check(mid,treeHeight,n,targetSum)){
                start = mid + 1;
                result = mid;
            }else{
                end = mid - 1;
            }
        }
        return result;
    }
    private static boolean check(int height, int[] treeHeights, int n,  int targetSum){
        long sum = 0;
        for(int treeHeight : treeHeights){
            sum += Math.max(treeHeight-height,0);
        }
        if(sum >= targetSum){
            return true;
        }else{
            return false;
        }
    }
}