BOJ 2343 - 기타 레슨

[jusung-c]

---

문제

문제 : https://www.acmicpc.net/problem/2343
난이도 : 실버 1

• 블루레이 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억)이므로 시간 안에 풀이 가능

---

이분 탐색의 범위를 처음에는 1~10억으로 잡고 했는데 틀렸다. 다른 사람 풀이를 보니 이분 탐색의 범위를 강의의 최대 길이부터 10억으로 잡았길래 그렇게 해보니 맞았다. 어짜피 1부터 강의의 최대 길이까지 Yes or No 결정 문제에서 No로 걸러질텐데 왜 틀렸는지 잘 모르겠다.. 😥

---

구현

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();
    }

}

---