43. 뮤직비디오

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

9 3

1 2 3 4 5 6 7 8 9

 

출력예제 1 

17

 

풀이 

- DVD 3개만으로 9개의 곡을 나누어 담아야함 

-모든 곡을 담을 때 필요한 용량은 1+2+3+4+5+6+7+8+9 즉, (9+10)/2인 45

- 1~45사이에 DVD한개의 최소 용량이 있다

- 정답이라고 유추한 mid값은 항상 maxx값 보다 커야 한다(DVD는 배열에서 가장 큰 용량을 가진 노래를 담을 수 있어야 하기 때문) 

 

ex) 1+45/2 = 23

(1,2,3,4,5,6),(7,8),(9)

-> res = 23, rt=22

 

23보다 더 작은 수가 최소 용량이 될 수 있음

-> rt를 mid-1 후 이분탐색함

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int a[1001], n;
// 43. 뮤직비디오(결정 알고리즘)

//필요 DVD 리턴
int Count(int s){
    int i, cnt=1, sum=0;
    for(i=1;i<=n;i++){
        if(sum+a[i]>s){
            cnt++; //DVD추가
            sum=a[i]; //초과된 DVD부터 sum count
        }
        else{
            sum+=a[i];
        }
    }
    return cnt;
}


int main() {
    int m, i, lt=1, rt=0, mid, res, maxx=-2147000000;
    scanf("%d %d", &n, &m);
    for(i=1;i<=n;i++){
        scanf("%d", &a[i]);
        rt=rt+a[i];
        if(a[i]>maxx) maxx=a[i]; //배열 중 가장 큰 값 찾기(DVD는 가장 큰 용량을 담을 수 있어야 함)
    }
    while(lt<=rt){
        mid=(lt+rt)/2; //dvd한 개의 최소 용량
        if(Count(mid)<=m && mid>=maxx){
            res=mid;
            rt=mid-1;
        }else{
            lt=mid+1;
        }
    }
    printf("%d\n",res);
    return 0;
}