결정 알고리즘 (이분탐색)

• 문제가 요구하는 답이 lt - rt 사이에 존재한다는 확신이 있을 때 사용하는 알고리즘
• 이분탐색을 응용하여 만들기 (오름차순 정렬 되어있어야함)

뮤직비디오 문제

설명

DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.

M개의 DVD에 모든 동영상을 녹화하기로 하였다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

입력

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

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

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

출력

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

예시 입력 1

9 3
1 2 3 4 5 6 7 8 9

예시 출력 1

17

설명 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다. 17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 녹화할 수 없다.

풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int capacity = 0;
        int lt = arr[n - 1];
        int rt = Arrays.stream(arr).sum();

        while (lt <= rt){
            int mid = (lt + rt) / 2;
            int result = isPossible(mid, arr);
            if (result <= m) {
                capacity = mid;
                rt = mid - 1; //중요!
            }else
                lt = mid + 1; //중요!
        }
        System.out.println(capacity);
    }

    private static int isPossible(int mid, int[] arr) {
        int cnt = 0;
        int sum = 0;
        for (int i : arr) {
            if (sum + i > mid) {
                cnt++;
                sum = 0;
            }
            sum += i;
        }
        cnt++;
        return cnt;
    }
}

• 주의! : 일반적인 이분검색과는 다르게 가능한 mid값을 찾았더라도 탐색을 이어간다 따라서 +1이나 -1을 해주어서 검색을 진행한 숫자는 제외하고 다음 탐색을 시작한다.

참고
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비