BOJ 2343 - 기타 레슨

 

문제

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

2343번: 기타 레슨

 

• 블루레이 N개의 강의 (녹화 순서 준수) (1 ≤ N ≤ 100,000)
• 블루레이 M개 (모두 같은 크기) (1 ≤ M ≤ N)
• 기타 강의 길이 리스트 - 분 단위로(자연수) <= 10000
• 블루레이의 크기(녹화 가능한 길이)를 최소

 

아이디어

강의가 총 9개이고 블루레이가 3개일 때, 

(1, 2, 3, 4, 5) (6, 7) (8, 9) 로 녹화하면 크기가 15, 13, 17이 된다. 

블루레이의 크기는 모두 같아야 해서 최소 크기가 17이 된다.

 

블루레이의 크기를 '최소' 해야 한다. ' 최소 ' 라는 키워드가 나왔으므로 이분 탐색으로 먼저 접근해보았다.

 

원래 문제

N개의 기타 강의를 M개의 블루레이에 녹화했을 때 가능한 블루레이의 크기 중 최소는 얼마인가?

 

이분 탐색을 위해 블루레이의 크기를 S 매개변수로 지정하고 문제를 뒤집어서 Yes Or No 결정 문제로 바꾼다.

 

뒤집어서 만든 Yes or No 문제

블루레이의 크기가 S일 때 N개의 기타 강의를 M개의 블루레이에 녹화할 수 있는가? Yes or No?

 

이분탐색

이분탐색의 범위는 블루레이 크기 범위이다. 최대치를 생각하면 최대 길이 10000인 100,000개의 강의이므로 10억까지 늘어날 수 있다. 따라서 이분탐색의 범위를 (강의 리스트 중 최대 길이 녹화본 ~ 10억)으로 잡는다. 그 후 이분탐색을 진행해 Yes or No를 채운 후 최소이므로 처음으로 Yes가 나온 값을 찾는다.

Yes or No 문제 풀이

먼저 순서대로 주어진 강의 리스트를 크기가 S가 될 때까지 더해준 후 블루레이 카운터를 하나 올려준다. 이런 식으로 끝까지 더해서 블루레이의 개수를 측정하고 M과 비교해 Yes or No를 결정한다.

 

 

시간 복잡도

• Yes or No 문제 풀 때 O(N)
• 이분 탐색 시 범위가 약 10억이므로 약 O(log 10억)
• 총 O(N log 10억)이므로 시간 안에 풀이 가능

 

 

구현

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] lecture;

    static void init() 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());

        lecture = new int[N + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            lecture[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        // 이분 탐색
        int L = lecture[1];
        for (int i = 1; i <= N; i++) {
            L = Math.max(L, lecture[i]);
        }
        int R = 1000000000;
        int ans = 0;

        while (L <= R) {
            int mid = (L + R) / 2;

            if (YesOrNo(mid)) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        bw.write(ans+" ");
    }

    // Yes or No 결정문제
    static boolean YesOrNo(int S) {
        int cnt = 1;
        int sum = 0;

        for (int i = 1; i <= N; i++) {
            // 강의 녹화하면 S 넘는지 확인
            if (sum + lecture[i] > S) {
                // 넘으면 cnt++
                cnt++;
                // 다음을 위해 새로 녹화(새로 0에 더해주기)
                sum = lecture[i];

            // 아니면 그대로 녹화(더해주기)
            } else {
                sum += lecture[i];
            }
        }

        return cnt <= M;
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}