백준 2343 - 기타 레슨 (자바 - 이분탐색)

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

* 문제 요약

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

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 갯수를 가급적 줄이려고 한다. 오랜 고민끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다.

이때, 블루레이의 크기(녹화 가능한 길이) 를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기여야 한다.

 

강토의 각 강의의 길이가 분 단위(자연수) 로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 강의의 수 N(1 <= N <= 100,000) 과 M (1 <= M <= N) 이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수) 로 주어진다. 각 강의의 길이는 10,000 분을 넘지 않는다.

 

* 출력

첫째 줄에 가능한 블루레이의 크기 중 최소를 출력한다.

 

* 예시

 

* 해결 과정

M개의 블루레이의 크기가 모두 같아야 하므로, 블루레이의 크기가 특정 값일 때 입력으로 들어온 강의들을 블루레이들 안에 모두 저장할 수 있는지 없는지 확인하고, 그 결과에 따라 이분탐색의 원리를 이용해 블루레이의 크기가 될 수 있는 범위를 절반씩 줄여가며 문제를 풀면 된다.

1. start 를 0, end 를 입력으로 들어온 강의의 총 길이값으로 초기화한다.

2. start <= end 조건을 만족하는 동안 다음과 같이 반복을 수행한다.

  - mid 를 (start + end) / 2 로 초기화한다. 이때 mid 는 M개의 블루레이의 공통된 크기에 해당된다.

  - check(int mid) 메소드를 수행한다.

    - 입력으로 들어온 강의들을 처음부터 탐색하며, 현재 블루레이에 저장된 강의의 길이 videoLength 와 현재 탐색중인 강의의 길이를 더했을 때 그 값이 mid 보다 작거나 같은 경우 videoLength 에 현재 탐색중인 강의의 길이를 더해준다.

    - 만약 mid 보다 큰 경우 블루레이의 갯수를 나타내는 변수 count 를 1 증가시킨다.

    - 이후 만약 count 가 M보다 큰 경우 반복문을 강제로 종료시킨다.

    - 그렇지 않을 경우 videoLength 를 0 으로 초기화 해주고, 다음 반복때 현재 탐색한 강의를 다시 한번 탐색하도록 인덱스 i값을 1 감소시킨다.

    - 반복문이 끝나고 난 후 videoLength 값이 0 이 아닌 상태라면 count 를 추가로 1만큼 증가시켜준다.

    - 이후 현재 count 값이 M보다 작거나 같다면 true 를 반환해준다.

    - 그렇지 않다면 false 를 반환해준다.

  - check(int mid) 메소드 수행결과 true 를 반환받은 경우 end 를 mid - 1 로 초기화하여 mid 가 더 작아지는 방향으로 범위를 줄여준다.

  - false 를 반환받은 경우 start 를 mid + 1 로 초기화하여 mid 가 더 커지는 방향으로 범위를 줄여준다.

3.반복문이 끝나고 나면 start 값을 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    static int N = 0;
    static int M = 0;
    static int[] lesson = null;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputArray = br.readLine().split(" ");
        N = Integer.parseInt(inputArray[0]);
        M = Integer.parseInt(inputArray[1]);

        lesson = new int[N];
        inputArray = br.readLine().split(" ");
        for (int i = 0; i < lesson.length; i++) {
            lesson[i] = Integer.parseInt(inputArray[i]);
        }

        int start = 0;
        int end = Arrays.stream(lesson).sum();

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

            if (check(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        bw.write(start + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean check(int mid) {

        boolean result = false;
        int count = 0; 
        int videoLength = 0;
        for (int i = 0; i < lesson.length; i++) {

            if (videoLength + lesson[i] <= mid) {
                videoLength += lesson[i];
            } else {
                count++;
                if (count > M) {
                    break;
                }
                videoLength = 0;
                i--;
            }
        }
        if (videoLength > 0) {
            count++;
        }

        if (count <= M) {
            result = true;
        }
        return result;
    }
}

 

블루레이의 최소 길이를 0, 최대 길이를 강의들의 길이를 총 합산한 값으로 초기 범위를 설정해준 뒤, 그 사이의 중간값을 블루레이의 공통된 크기로 하였을 때 강의들을 M개의 블루레이 안에 저장시켜 줄 수 있는지 없는지에 따라 범위를 절반씩 줄여가며 답을 찾았으므로 매개변수 탐색 문제에 해당된다.