[알고리즘]Searching - 뮤직비디오(결정 알고리즘)

9. 뮤직비디오(결정알고리즘)
DVD의 최소 용량 크기(녹화 가능한 길이)를 구하는 프로그램

입력) 첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어집니다.
다음 줄에는 곡의 길이가 분 단위로(자연수) 주어집니다.
출력) 첫 번째 줄부터 DVD의 최소 용량 크기를 출력합니다.

 

 

import java.util.Arrays;
import java.util.Scanner;

public class Main { // Binary Search
	
	public static int count(int[] arr, int capacity) { // dvd 몇 장 필요한지
		int cnt = 1, sum = 0; // cnt : 필요한 dvd 장 수 // sum : 노래 길이
		
		for (int x : arr) {	
			if (sum+x>capacity) {
				cnt++;
				sum = x;
			} else {
				sum += x;
			}
		}
		return cnt;
	}
	
	public static int solution(int n, int m, int[] arr) {
		int answer = 0;	
		int lt = Arrays.stream(arr).max().getAsInt(); // 배열의 최댓값
		int rt = Arrays.stream(arr).sum(); // 배열의 합
		
		while (lt<=rt) {
			int mid = (lt+rt)/2;
			if (count(arr,mid)<=m) {
				answer = mid;
				rt = mid-1;
			} else { // 용량이 더 커야 함
				lt = mid+1; 
			}
		}		
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); // 총 곡의 개수
		int m = scanner.nextInt(); // 총 DVD 개수
		int[] arr = new int[n]; // 부른 곡의 길이 배열
		for (int i=0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		System.out.println(solution(n,m,arr));
	}

}

* Stream : 컬렉션의 요소를 하나씩 참조해서 람다식으로 처리할 수 있게 해주는 반복자

예1) Arrays.stream(배열명).max() : 배열의 최댓값
예2) Arrays.stream(배열명).sum() : 배열의 합

---

결과

입력
9 3
1 2 3 4 5 6 7 8 9

출력
17