뮤직비디오 문제 (결정알고리즘) 풀이

문제:

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.

DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.

순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는

1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.

지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.

고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

 

입력:

첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.

다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.

부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

 

출력:

첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

입력예시:

9 3
1 2 3 4 5 6 7 8 9

 

출력예시:

17

 

 

개인 해설:

문제를 풀때 우선적으로 해야 하는것은 이분탐색을 위한 lt(start) , rt(end), mid를 정하는 것이다.

lt는 최소값인것은 알겠는데 어떤 기준으로 설정하면 될까?

lt는 비디오 하나를 담을 수 있는 최소한의 크기이다.! 그렇다면 

1 2 3 4 5 6 7 8 9 이러한 비디오 용량중 가장 높은 9를 설정하면 어떠한 비디오가 들어와도 담을 수 있기 때문에 lt는 9로 설정한다.

rt는 최대값을 구해야 한다. 모든 노래를 한 비디오에 담는것이 최대값이 될 것이기 때문에 1 2 3 4 5 6 7 8 9 을 모두 더한 값인 45로

rt를 설정한다.

lt와 rt를 구했다면 mid는 공식에 의해 27로 계산된다. mid = (lt+rt) / 2

lt,rt,mid 값 지정이 끝났다면 본격적으로 해를 구할텐데, 위 입력예시 처럼 m=3이면 3개의 뮤직비디오를 담기위해 최소 용량을 묻고있다.

아래 코드와 같이, 원하는 값을 구할때까지 이분탐색을 반복해서 해를 구할 수 있다.

while (lt<=rt){
    int mid =(lt+rt)/2;
    // *** 중요 : m이 3일때 count()return값이 2가 나왔다고 했을때,  2개의 비디오를 만들 수 있다는 말은
    // 용량을 3개의 비디오도 만들 수 있다는 말이다. 때문에 용량을 줄여서 다시 계산하도록 한다.
    if(count(arr,mid)<=m){
        rt=mid-1;
        answer = mid;
    }
    else lt = mid+1;
}

 

count(arr,mid) 함수는 주어진 mid값으로 몇개의 비디오를 만들 수 있는지 출력하는 함수이다.

public int count(int[]arr,int mid){
    int res=1; //최소 1개의 비디오는 만들어지므로 1로 초기화
    int sum=0;
    for(int i : arr){
        if(sum+i > mid){
            res++;
            sum=i;
        }
        else sum += i;
    }
    return res;
}

 

최종적으로 정답인 17이 출력되는 것을 확인할 수 있으며, count()함수에 아래와 같은 출력코드로 확인해보면

System.out.println("mid: "+mid+" , "+"res:"+res);

해를 구하기 위해 반복적으로 이분탐색하는 것을 확인할 수 있다.

 

 

 

 

문제출처 : 인프런 - 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 [김태원]