코딩 테스트 [탐색] - 블루레이 만들기

강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때 레슨의 순서가 바뀌면 안된다. 순서가 뒤바뀔 때는 레슨의 흐름이 끊겨 학생들이 혼란에 빠질 수 있기 때문이다. 즉 i,j번 레슨을 같은 블루레이에 녹화하려면 i와 j사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없어 제작 개수를 가급적 줄이려고 한다. 강토는 고민 끝에 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다. 이때 블루레이의 크기(녹화할 수 있는 길이)는 최소, M개의 블루레이는 모두 같은 크기로 만들려고 한다.

강토의 각 레슨의 길이가 분 단위(자연수)로 주어질 때 가능한 블루레이의 크기 중 최솟값을 구하는 프로그램을 작성하시오

(시간 제한 2초)

---

입력

1번째 줄에 레슨의 수 N(1 ≤ N ≤ 100,000)과 블루레이의 개수 M(1 ≤ M ≤ N), 2번째 줄에 강토의 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수) 주어진다. 각 레슨의 길이는 10,000분을 넘지 않는다.

출력

1번째 줄에 블루레이의 총 크기 중 최솟값을 출력한다.

예제 입력
9 3		// 레슨 수, 블루레이 개수
1 2 3 4 5 6 7 8 9

예제 출력
17

---

1단계 - 문제 분석하기

블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 선택하게 하는 실마리이다. 블루레이에 첫 레슨부터 마지막 레슨까지 차례대로 저장하다 보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다. 모두 저장할 수 있다면 블루레이 크기를 줄이고 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 블루레이 크기의 최솟값을 알 수 있다.

2단계 - 손으로 풀어 보기

1 이진 탐색의 시작 인텍스는 최대 길이의 레슨이고 종료 인덱스는 모든 레슨 길이의 합이다. 총 9개로 구성된 레슨의 시간은 각각 1, 2, 3, 4, 5, 6, 7, 8, 9이므로 이진 탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다. 블루레이 개수가 3일 때 9 ~ 45 사이에서 블루레이 크기의 최솟값을 이진 탐색으로 찾으면 된다.

2 9 ~ 45 사이에서 이진 탐색을 수행한다. 이진 탐색은 시작 인덱스 > 종료 인덱스일 때까지 수행한다.

이진 탐색 수행

• 중앙값 크기로 모든 레슨을 저장할 수 있으면 종료 인덱스 = 중앙값 - 1(왼쪽 데이터셋)
• 중앙값 크기로 모든 레슨을 저장할 수 없으면 시작 인덱스 = 중앙값 + 1(오른쪽 데이터셋)
  

3단계 - sudo코드 작성하기

N(레슨 개수) M(블루레이 개수)
A(기타 레슨 데이터 저장 배열)
start(이진 탐색 시작 인덱스)
end(이진 탐색 종료 인덱스)

for(N의 개수만큼 반복)
{
	A배열 저장
    시작 인덱스 저장(A 배열 중 최댓값)
    종료 인덱스 저장(A 배열의 총합)
}

while(시작 인덱스 <= 종료 인덱스)
{
	mid(중간 인덱스)
    sum(레슨 합)
    count(현재 사용한 블루레이 개수)
    
    for(N의 개수만큼 반복하기)
    {
    	if(sum + 현재 레슨 시간 > 중간 인덱스)
        {
        	count++
            sum = 0
        }
        sum에 현재 레슨 시간값 저장
    }
    
    if(sum이 0이 아님)
    	count++ (마지막 블루레이가 필요하므로)
        
    if(count > M)
    	시작 인덱스 = 중앙 인덱스 + 1
    else
    	종료 인덱스 = 중앙 인덱스 - 1
}

시작 인덱스 출력

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q30 {
    static int N;
    static int M;
    static int[] A;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        int start = 0;
        int end = 0;

        A = new int[N];
        for(int i = 0; i < N; i++){
            A[i] = sc.nextInt();
            if(start < A[i])
                start = A[i];
            end += A[i];
        }

        while(start <= end){
            int mid = (start + end) / 2;
            int sum = 0;
            int count = 0;

            for(int i = 0; i < N; i++){
                if(sum + A[i] > mid){
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }

            if(sum != 0)
                count++;

            if(count > M)
                start = mid + 1;
            else
                end = mid - 1;
        }

        System.out.println(start);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편