[백준 2343] 기타 레슨

 

이분 탐색으로 문제에서 요구하는 블루레이 크기를 구하는 문제다.

 

1. 최소값은(left) 레슨의 수 중 가장 작은값으로 한다.

2. 임의로 정한 블루레이 크기((left + right)/2)에 레슨을 순차적으로 담는다.

2-1. 레슨의 길이가 블루레이의 크기를 초과하게 된다면 블루레이 크기를 증가시킨다.

3. 블루레이의 개수가 m 보다 작다면 최대값(right)를 줄인다.

3.-1. 블루레이의 개수가 m 보다 같거나 크다면 최소값을 줄인다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        
        int left = 0;
        int right = 0;
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            right += a[i];
            left = left < a[i] ? a[i] : left;
        }
        
        while(left <= right) {
            int mid = (left + right)/2;
            int sum = 0;
            int cnt = 0;
            for(int i=0; i<n; i++) {
                if(sum + a[i] > mid) {
                    sum = 0;
                    cnt++;
                }
                sum += a[i];
            }
            if(sum != 0) cnt++;
            if(cnt <= m) right = mid-1;
            else left = mid+1;
        }
        System.out.println(left);
    }
}