백준 1654 - java

 

import java.util.Scanner;

public class BJ1654 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //랜선의 갯수
        int k = sc.nextInt();
        //필요한 랜선의 갯수
        int n = sc.nextInt();

        int[] arr = new int[k];

        //배열 입력받기.
        for (int i = 0; i < k; i++) {
            arr[i] = sc.nextInt();
        }
        
        //결과
        long result = 0;
        //시작
        long left = 1;
        //끝
        long right = 0;

        // 최대 길이 계산
        for (int i = 0; i < k; i++) {
            right = Math.max(right, arr[i]);
        }
        
        while (left <= right) {
            long mid = (left + right) / 2;
            if (checking(arr, mid, n)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(result);
    }
    public static boolean checking(int[] arr, long length, int n) {
        long count =0;
        for (int i : arr) {
            count+=i/length;
        }
        return count >=n;
    }

}

 

문제를 보고 머릿속으로 그려보다가 이거 search를 사용해야 할 것 같다는 느낌을 받았고 그에 따라 logN의 시간복잡도를 가지고 있는 BinarySearch 가 떠올랐다. 그래서 그걸 기반으로 코딩을 했으나 right를 어떻게해야할지 고민이였고 계속 시도를 하였지만 오류가 나서 고민을 하다가 재귀적으로 찾아보면 어떨까 싶어서 다음과 같이 코드를 작성하고 마무리 하였다.