0609

import java.util.*;
public class Main {

    public static int count(int[] arr, int capacity){
        // dvd 1장 용량이 capacity 이면 dvd 몇장이   필요한가?
         int cnt = 1;
         int sum = 0;
         for (int x : arr){
             if (sum+x>capacity){
                 cnt+=1;
                 sum=x;
             } else {
                 sum+=x;
             }
         }
         return cnt;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];

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


        //n개의 노래를 m개의 dvd에 담을 때 최소 길이
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).sum();
        int answer = 0;

        while (lt<=rt){
            int mid = (lt+rt)/2;
            if (count(arr,mid)<=m){
                answer = mid;
                rt = mid-1;
            } else {
                lt = mid+1;
            }
        }

        System.out.println(answer);






        return ;
    }
}

• lt랑 rt 사이에 답이 있는 경우에 사용함
• 최적의 답을 찾아 나감
• O(logn)의 시간복잡도

0610

import java.util.*;
public class Main {

    public static int count(int[] arr, int distance){
        int ep = arr[0];
        int c = 1;
        for (int i=1; i<arr.length; i++){
            if (arr[i]-ep>=distance){
                ep = arr[i];
                c+=1;
            }
        }

        return c;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int c = in.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++){
            arr[i] = in.nextInt();
        }

        //마구간 좌표 정렬
        Arrays.sort(arr);

        int lt = 1;
        int rt = Arrays.stream(arr).max().getAsInt();
        int answer = 0;

        while (lt<=rt){
            int mid = (lt+rt)/2;
            if (count(arr,mid)>=c){
                answer = mid;
                lt = mid+1;
            } else {
                rt = mid-1;
            }


        }

        System.out.println(answer);





    }
}