뮤직비디오(결정알고리즘)

문제

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지
되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번
노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야
한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는
DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기
로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는
모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

제한사항

입출력 예

풀이

// cd의 개수를 count 해줄 함수
function count(songs, capacity) {
  let cnt = 1,
    sum = 0;
  for (let x of songs) {
    // sum에 x값을 더하면서 누적해나가다가
    // capacity를 넘어서면 cd의 개수를 올려주고
    // sum값을 갱신해준다.
    if (sum + x > capacity) {
      cnt++;
      sum = x;
    } else {
      sum += x;
    }
  }

  return cnt;
}

// 메인 솔루션
function solution(m, songs) {
  let answer;
  // cd의 최소 분은 노래의 길이 중 가장 긴 값.
  let lt = Math.max(...songs);
  // cd의 최대 분은 모든 노래 길이의 합.
  let rt = songs.reduce((a, c) => (a += c), 0);

  // 이분탐색
  // mid값을 capacity로 했을 때 cd의 개수가 몇개 나오는지 확인
  // 이 때, cd의 개수는 m 이하가 되어야하는데 이 조건을 만족하는 최소 mid값
  while (lt <= rt) {
    let mid = Math.floor((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));

코드에 대한 해석은 주석을 참고하자.

코드의 진행과정을 따라가면 처음 mid값은 27이 된다. 그리고 이 값을 capacity로 한 count 함수의 결과는 2가된다.
27분 짜리 cd로 만들면 2개가 나온다는 뜻이다. 이 경우 m, 3보다 작기때문에 27은 답이 될 수 있다. 다만 최선의 답은 아닌 것이다.
mid 값을 더 줄여서 최선의 답을 찾을 수 있는 것. 이것이 결정 알고리즘의 포인트이다.

그렇게 mid값이 17까지 내려가게 되고, cd는 3개가 나온다. 역시 답이 될 수 있기에 mid값은 더 작아진다.
다음 mid값은 12 이때는 cd가 3개 이상이 나온다. 이러면 mid값은 올라간다. 14 16 까지 올라가도 결국 17보다 최적의 해를 찾을 수 없어서 답은 17이 된다.