[알고리즘 연습] 콘서트 동영상 저장하기

라이브 동영상

• N(1<N<1000)개의 노래를 부른 콘서트의 라이브 동영상을 끊어서 M(1<M<N)개의 DVD에 저장하려고 한다.
• 노래 순서는 처음 주어진 상태에서 변경하면 안된다.
• 각 노래의 시간이 분단위로 주어진다. (최대 10000분)
• 각 DVD의 저장시간은 동일하다.
• 이 때 N개의 노래를 M개의 DVD에 담을 수 있는 DVD의 최소 용량을 구하시오(용량은 분단위로 표현)
• ex. N=9, M=3, (1,2,3,4,5,6,7,8,9)로 값이 주어졌을 경우 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 저장할 수 있다. 17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 저장할 수 없다. 따라서 답은 17.

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a;
int n;

int Count(int s) {
    int i, cnt=1, sum=0;
    for(i=0;i<n;i++) {
        if (a[i]>s) {
            return 10001;
        }
        if(sum+a[i]>s) {
            cnt++;
            sum=a[i];
        } else {
            sum+=a[i];
        }
    }    
    return cnt;
}

int main() {
    int m, i, temp, start=1, end=0, mid, res;
    cin>>n>>m;

    for(i=0;i<n;i++) {
        cin>>temp;
        a.push_back(temp);
        end+=temp; 
    }

    while(start<=end) {
        mid=(start + end)/2;
        if(Count(mid)<=m) {
            res=mid;
            end=mid-1;
        } else {
            start=mid+1;
        }
    }    

    cout << res;

    return 0;
}

• 결정알고리즘과 이진탐색을 응용하여 해결한다. (결정알고리즘 : 답을 결정해놓고 해당 답이 문제의 조건에 맞는지 확인하여 해결하는 방법)
• 결국 DVD 용량의 답은 1~노래길이의총합 사이에 있을 것이므로 그를 응용하여 이진탐색을 실시한다.
• mid값이 정답이 될 수 있는지 Count 함수를 사용해 확인한다. Count 함수는 해당 DVD 용량을 사용했을 때 최소 몇개의 DVD가 필요한지 리턴하는 함수이다. 이를 M값과 비교해서 같거나 작다면 가능한것으로 처리한다.
• 해당 과정을 모두 마쳤을 때의 res값이 최소용량이된다.
• 문제가 조금만 복잡해도 자꾸 더 쉬운방법을 찾으려는 습관이 있다. 빠르게 구현가능한 정도라면 거기까진 구현해보자.
• 결정 알고리즘은 잘 활용할 수 있을 것같으니 익혀두자.