(인프런)알고리즘문제풀이-6.9뮤직비디오(결정알고리즘)

첫번째 아이디어

이분탐색은 정렬이 되어있는 상태에서 사용할 수 있다.
최소와 최대값은 9 <-> 45이다.
최소와 최대값을 더한 45+9 = 54 / 2를 최소의 용량이라고 생각하고 각각의 노래를 연속해서 담을 수 있는지 확인한다.

좁혀나가면서 최종적으로 선택된것이 결정알고리즘이다.
27이 된다면 26으로 다시 확인하고 된다면 다시 1을 빼서 계속적으로 최적의 정답을 찾아간다.

package Java.InflearnJavaStudy.Sorting_Searching;

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

public class Ex_0609 {
    public int solution(int n, int m, int[] arr) {
        //9 3
        //1 2 3 4 5 6 7 8 9
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt(); //해당 배열에서 가장 큰수 찾아주는것
        int rt = Arrays.stream(arr).sum(); // 해당 배열을 전부 합한것

        while(lt<=rt) {
            int mid = (lt+rt)/2; //dvd한장의 용량이다.

            if(count(arr, mid)<=m) {//리턴한 dvd장수가 m보다 작거나 같으면 만족하는 용량이다.
                answer = mid;
                rt = mid-1;
            }
            else {//lt가 rt보다 커지면 멈추면된다.
                lt = mid+1;
            }
        }

        return answer;
    }

    public int count(int[] arr, int capacity) {
        int cnt  = 1; //dvd장수
        int sum = 0; //dvd의 곡들의 합
        for(int x : arr) {
            if(sum+x > capacity) {
                cnt++;
                sum=x;
            } else {
                sum+=x;
            }
        }
        return cnt;
    }

    public static void main(String[] args){
        Ex_0609 T = new Ex_0609();
        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();
        }
        System.out.print(T.solution(n,m,arr));
        return ;
    }
}

• 지속적으로 몇장이 필요한지를 찾아주는것은 cnt이고, sum과 x를 이용해서 최솟값에 부합하는지를 조건으로 확인하는 과정을 가진다.

출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비