뮤직비디오(결정 알고리즘), 이분검색

코드

  function count(songs, mid) {
    let album = 1,
      sum = 0;

    for (let x of songs) {
      if (sum + x > mid) {
        album++;
        sum = x;
      } else sum += x;
    }

    return album;
  }

  function solution(m, songs) {
    let answer;

    let lt = Math.max(...songs),
      rt = songs.reduce((a, b) => a + b, 0);

    while (lt <= rt) {
      let mid = parseInt((lt + rt) / 2);
      let result = count(songs, mid);

      if (result <= m) {
        answer = mid;
        rt = mid - 1;
      } else lt = mid + 1;
    }

    return answer;
  }

해결 방법

이 문제는 이분 검색으로 해결할 수 있는 문제이다. 

count 함수

count 함수는 각 mid 값에 따라서 album의 개수가 몇개 나오는지 구하는 함수이다.

solution 함수

1. DVD 용량의 범위는 [가장 긴 노래의 길이, 전체 노래의 합]이다. 따라서 lt에 가장 긴 노래의 길이, rt에 전체 노래의 합을 넣는다.

2. while문을 lt <= rt일때까지 돌린다. 그리고 mid는 lt와 rt의 중간값을 넣고 result에는 최신화 된 mid를 가지고 count 함수의 결과를 저장한다.

 

-result <= m인 경우

m은 원하는 DVD의 개수이다. 

result가 m보다 작거나 같으면 answer에 mid를 항상 최신화한다. 왜냐하면 while문을 돌릴때마다 최적의 답에 다가가고 있기 때문이다. 그리고 rt에는 mid+1의 값을 넣어준다. 왜냐하면 DVD를 더 적게 했으므로 mid의 값을 줄여줘야 되기 때문이다.

 

-result > m인 경우

이 경우에는 answer최신화를 하면 안된다. 그리고 DVD를 많이 나오게 했으므로 mid의 값을 늘려야한다.