결정 알고리즘, 이분탐색_뮤직비디오

🔵 ThingsILearned

✔️ 결정 알고리즘

답을 x라고 생각하고 x가 유효한지 확인해 가면서 더 좋은 답을 찾는 알고리즘 특정 범위 안에 x가 존재한다는 확신이 있어야 함.

따라서 문제의 경우 1~9까지 3개의 그룹에 넣을 것인데,
최소 9부터 최대 45(1부터 9까지의 합)사이에 답이 있을 것이므로 9~45사이에서 결정알고리즘을 사용한다.

✔️ Arrays.stream()

int start= Arrays.stream(input).max().getAsInt(); //array내에서 최대값 구하기
int end= Arrays.stream(input).sum(); //array합 구하기

max는 object integer을 리턴하기 때문에 .getAsInt()를 해 주어야 한다.
근데 또 sum()은 integer리턴해서 .getAsInt()필요 없음

✅ 뮤직비디오

라이브에서 순서대로 부른 곡의 길이가 분 단위로 주어졌을 때
m개의 dvd안에 노래들을 저장하려고 한다.
단, 라이브에서 부른 순서대로 저장해야 하고 모든 dvd는 같은 길이어야 한다.
또한 노래를 쪼개서 저장할 수 없다.
이 때 dvd 최소 용량을 구하세요

길이가 n인 숫자 리스트가 있을 때, 총 m개의 그룹으로 리스트를 나눠야 한다.
m개의 그룹으로 리스트를 나눴을 때, 한 그룹당 최소 얼마의 숫자합이 되는지 구하세요.
숫자 리스트 순서대로 그룹에 들어가야 하며,
모든 그룹의 크기가 같다야 한다고 할 때, 한 그룹의 최소 크기를 구하세요
단, n개 숫자 리스트를 중간에 나눌 수 없다.
1,2,3 으로 하나의 그룹에 들어가기 가능 ⭕️
그러나 1, 2, 2.5 까지 한 그룹에 들어가기 불가능 ❌

class Main {
    public int countDVD(int middle, int[] input){ //DVD 몇 개 쓰였는지 return
        int count=1;
        int sum=0;
        for(int x: input){
            if(sum +x > middle){ //새로운 값 x를 더했을 때 middle보다 크다면
                count++; //새로운 dvd에 저장
                sum=x;
            }else{
                sum +=x;
            }
        }
        return count;
    }
    public int solution(int n, int m, int[] input){
        int answer=0;
        int start= Arrays.stream(input).max().getAsInt(); //array내에서 최대값 구하기
        int end= Arrays.stream(input).sum(); //array합 구하기
        while(start <= end){ //binary search
            int middle= (start+end)/2;
            if(countDVD(middle, input) <= m){ //사용된 DVD개수가 m보다 작다면
                answer= middle;
                end=middle-1; //배열에서 더 작은 값 탐색하기
            }else{
                start= middle+1; //배열에서 더 큰 값 탐색하기
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int m= sc.nextInt(); //사용하고 싶은 dvd개수
        int[] input= new int[n];
        for(int i=0; i<n; i++){
            input[i]= sc.nextInt();
        }
        System.out.print(T.solution(n, m, input));
    }
}
//⭐️input:
9 3
1 2 3 4 5 6 7 8 9
설명 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다.
//⭐️output:
17

✔️ solution함수

1️⃣ 결정 알고리즘

1. 결정 알고리즘을 사용한다.
   
2. 결정 알고리즘 사용을 위해서 답이 있을만한 최소값과 최대값을 구해서 그 사이를 탐색해야 함
   
3. 최소값: 가장 긴 노래(배열에서 가장 큰 값)
   
4. 최대값: 모든 노래들을 합한 값(배열안 모든 숫자들의 합)
   

2️⃣ 이분 탐색 시작
5. 이분 탐색을 위해 최소값이 최대값보다 작은 동안
6. 중간값 구하기
7. 사용된 dvd의 개수가 우리가 사용하려고 했던 m개보다 작다면, 이 중간값은 유효한 값이다.
8. 따라서 answer에 저장
9. 더 좋은 값이 있을 수 있으니 탐색
10. 만약 중간값이 유효하면 배열에서 더 작은 값들 탐색
11. 중간값이 유효하지 않으면 중간값이 더 커야한다는 거니까 배열에서 더 큰 값들 탐색

✔️ 유효성 검사 함수 countDVD

1. 중간값(middle)은 dvd의 최소 크기라고 생각하는 값이다.
   
2. sum 에다가 배열에 있는 x를 쭉쭉 더하는데
   
3. 더하다가 중간값보다 커지면? 그러니까 dvd용량보다 크면? 노래를 더이상 저장할 수 없다.
   
4. 따라서 새로운 dvd에 저장, count++하고 sum=x 해서 새로운 dvd에 노래 저장
   
5. sum 에다가 x를 더했는데 dvd용량보다 작으면 계속 더하면 됨.
   
6. 마지막으로 count를 리턴함.