결정알고리즘 연습 1

결정알고리즘

조건 : 대상의 범위가 정렬 되어 있어야 한다.

1. 범위를 통해 시험할 값을 결정 (아래의 예제는 부분합(DVD의 크기 값)을 대상으로 설정)

2. 유효성을 검사하기 위한 로직을 작성 (Count 를 제대로 작성하는 것이 중요.)

3. 유효성 검사 및 이분 검색을 활용하여 최적화된 값을 찾아간다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;




class Main {

	static int answer = 0;
	
	public static void main(String args[]) throws Exception {
		
		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();			
		} 
		
		
		
        //답이 될 수 있는 후보를 lt, rt로 각각 초기화한다.
        //멤버 중 가장 큰 값을 최소, 모든 요소의값을 다 담을 수 있는 크기를 최대로 한다.
		int lt = Arrays.stream(arr).max().getAsInt() ;
		int rt = Arrays.stream(arr).sum();
		int min = Integer.MAX_VALUE ;
		
		
		while (lt <= rt) {
			
			int mid = (lt+rt)/2;
			int sum =0;
			
			int cnt = 1;		
			for ( int x : arr) {
				if( sum +x > mid) {
					cnt++;
					sum = x;
				} else sum +=x;
			}
			
			//System.out.println("cnt : "+ cnt + " sum : "+sum + " idx : "+idx);			
			if  (cnt <= m) {
				min = Math.min(min, mid);
				rt = mid - 1;
			} else {				
				lt = mid + 1;				
			}
		}
		
		
		System.out.println(min);
	}
		
		
	
}

ex)
input
9 3
1 2 3 4 5 6 7 8 9

output
17