2022/03/23) 11. 뮤직비디오(결정알고리즘) [정렬과 그리디, 결정알고리즘]

1. 문제

<뮤직비디오>
: 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, 라이브에서의 순서가 그대로 유지 되어야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하려 하는데, 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기로 해야 한다.
DVD의 최소 용량 크기를 출력하라.
(문제가 이해하기 좀 어려웠는데 그냥 DVD개수를 M개로 맞추고, DVD의 최대 크기가 같으면 된다는 거인 듯. 한 마디로 3개의 DVD 최대 크기가 같아야 함. 최대한 작은 용량을 구하는 게 핵심인 듯.)
!!! 결정알고리즘의 기본 베이스는 이분탐색이라고 함

2. 해결 방법

1. DVD의 크기가 같아야 하니까, 곡들 중 가장 긴 곡을 DVD의 최소 크기로 한다. (가장 긴 곡도 DVD에 들어가야 하므로)
2. DVD의 용량을 구하여야 하므로, DVD의 용량을 이분탐색으로 구할 건데, lt를 DVD의 최소 크기, rt를 DVD를 다 합한 값으로 한다. 그리하여 mid는 (lt+rt)/2 값으로 한다.
3. lt가 9이고 rt가 45면 mid는 27이 된다. 그리하여 곡들을 DVD에 넣어보면, DVD용량 27에 1~6/7~9로 총 2장이 들어간다. 3개씩 나눠서 넣어서 DVD용량 27로 결론을 내릴 수도 있지만, 우리가 구해야 하는 것은 DVD의 최소 용량이므로, 27을 answer에 넣고 이분탐색을 통해 또 다음 것들을 해본다.
   ! DVD가 몇 개 필요한지 검사하는 cout함수, DVD의 최대 용량을 구하는 solution함수.

! 전개 연산자(...)

• spread 연산자가 그냥 깊은 복사(주소 복사X, 독립적으로 됨)만 되는 줄 알았는데, 배열이나 객체의 모든 속성을 풀어놓을 수도 있다고 한다.
  밑에서 배열의 최댓값을 구할 때 전개 연산자를 사용했다.

3. 정답

        <script>
            function count(songs, capacity){ //mid값을 capacity에 넣기
                let cnt = 1, sum = 0; //DVD장수(무조건 한 장은 있어야 저장할 수 있으므로)와 한 DVD에 들어가는 곡들의 합. sum(곡들의 합)이 mid값(용량)을 넘어서면 cnt++해줘야함
                for(let x of songs){
                    if(sum+x > capacity){ //저장할 수 없다. 두 번째 DVD에 담는다. >= 는 안됨. 왜냐면 조건을 >=로 줘버리면, 그 값이 다음 DVD에 들어감
                        cnt++;
                        sum = x; //그러므로 두 번째 DVD는 값을 x로 초기화함
                    }
                    else sum+=x;
                }
                return cnt;
            }
            function solution(m, songs){
                let answer;
                let lt = Math.max(...songs); //max는 원래 인자가 넘어가야 함. 그래서 ...(스프레드연산자)를 사용하면 인자로 넘어감 (songs[0], songs[1],...)이런 식으로 펼쳐짐. 전개연산자!!! 
                let rt = songs.reduce((a,b) => a+b, 0);
                while(lt <= rt){
                    let mid = parseInt((lt+rt)/2);
                    if(count(songs, mid) <= m){
                        answer = mid;
                        rt = mid-1;
                    }
                    else lt = mid+1;
                }
                return answer;
            }
            let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9];
            console.log(solution(3, arr));
        </script>