[BOJ/JAVA] 2343번: 기타 레슨

키워드

• 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.

• M개의 블루레이에 모든 기타 강의 동영상을 녹화하

• 블루레이의 크기(녹화 가능한 길이)를 최소

• M개의 블루레이는 모두 같은 크기

---

구현

• 블루레이 크기를 매개변수로하여 이분 탐색을 진행한다.

• lectures[]
  • 강의의 누적합

• low = 가장 긴 길이의 강의

• high = 모든 강의 길이의 합

• canMake()
  • mid = (low+high)/2 의 블루레이 크기로 녹화할 수 있는지 체크
  • 0부터 누적합을 계산하며 진행한다.
  • mid보다 커지는 순간 → 현재 인덱스의 강의를 제외한 이전 강의를 현재 블루레이에 담는다.
  • 마지막 인덱스가 아닌데, 블루레이의 수가 M이상이라면 .. false 반환
  • 반복문이 끝난 경우 → 디스크가 남는 경우
    • 디스크의 크기는 항상 한 개의 강의를 넣을만큼 충분하다.
    • 앞의 강의를 적절하게 당겨서 분배한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class java_2343 {
    // 강의의 수 (N)
    // 블루레이의 수 (M)
    static int N, M;

    static int lectures[];

    // size로 모든 강의를 담을 수 있는가?
    static boolean canMake(int size) {
        // 이전 누적합
        int preSize = 0;

        int blueLayCount = 0;

        for (int i = 0; i < N; i++) {
            if (size < lectures[i] - preSize) {
                // i-1까지 담을 수 있다.
                preSize = lectures[i - 1];
                // 블루레이 1장 소모
                blueLayCount++;

                // 가진 블루레이의 수를 초과했다면..
                if (i <= N - 1 && blueLayCount >= M) {
                    return false;
                }
            }
        }
        // 디스크가 남는다 -> 이전 강의를 남은 디스크에 분배.(어처피 최소 1개는 들어갈 수 있도록 용량을 조절하므로..)
        //

        return true;
    }

    static int solution(int maxLength) {
        int result = 0;

        int low = maxLength;
        int high = lectures[N - 1] + 1;

        while (low < high) {
            // 블루레이를 mid 크기로 만들 수 있는가?
            int mid = (low + high) / 2;

            boolean able = canMake(mid);

            if (able) {
                high = mid;
                continue;
            }

            low = mid + 1;
        }

        System.out.println(low);

        return result;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        lectures = new int[N];
        st = new StringTokenizer(br.readLine());
        lectures[0] = Integer.parseInt(st.nextToken());
        int maxLength = 0;
        for (int i = 1; i < N; i++) {
            int lecture = Integer.parseInt(st.nextToken());
            if (maxLength < lecture) {
                maxLength = lecture;
            }
            lectures[i] = lectures[i - 1] + lecture;
        }

        int result = solution(maxLength);

        br.close();
    }
}

---

Uploaded by N2T