[BOJ] 백준 2343 - 기타 레슨 풀이

1. 문제

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

2343번: 기타 레슨

 

2. 풀이

이분 탐색을 활용한 문제이다. 문제를 해결하면서 탐색을 해야할 대상을 어떻게 잡아야 할지 생각을 해도 모르겠어서 다른 분들의 풀이를 참고하였다. 

이 문제에서 탐색해야 할 것은 블루레이의 크기이다. 입력 값이 예제 입력 1과 같고 블루레이의 크기가 10이라고 가정해보자. 앞에서부터 레슨을 더해본다면 1 + 2 + 3 + 4 = 10 다음에 5를 더하면 15가 되기 때문에 하나의 블루레이에 5는 들어갈 수 없고 4까지만 들어갈 수 있다. 나머지 레슨도 더하여 10이 넘는지 판단하면 레슨은 {1, 2, 3, 4}, {5}, {6}, {7}, {8}, {9}  == > 6개가 된다. 이러면 블루레이의 입력 값인 3이 아니므로 답이 될 수 없고 블루레이의 크기를 늘려야 한다.

그렇다면 이분 탐색을 하려면 left, right 값을 정해야 하는데 어떤 값이 들어가야 할까?

결론부터 말하면 left에는 입력으로 주어진 값 중 가장 큰 값, right에는 입력으로 주어진 값의 합이 된다.  이유는 left의 경우 가장 큰 값보다 작을 경우 블루레이에 못 담는 레슨이 생기고, 큰 경우 최소 값이 아닐 수 있기 때문이다. right의 경우 입력 값을 다 더한 값이 블루레이의 크기가 된다면 1개의 블루레이에 모든 레슨을 담을 수 있기 때문이다.

 

3. 소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 강의 수
        int M = Integer.parseInt(st.nextToken()); // 블루레이 수

        long left = 0;
        long right = 0;

        st = new StringTokenizer(br.readLine());
        int[] lesson = new int[N];
        for (int i = 0; i < N; i++) {
            lesson[i] = Integer.parseInt(st.nextToken());
            left = Math.max(left, lesson[i]);
            right += lesson[i];
        }

        long mid = 0;

        while (left <= right) {
            long tempSum = 0;
            int cnt = 0;

            mid = (left + right) / 2;
            for (int i = 0; i < N; i++) {
                tempSum += lesson[i];

                if (tempSum > mid) {
                    tempSum = lesson[i];
                    cnt += 1;
                }
            }
            if (tempSum > 0) {
                cnt += 1;
            }
            if (cnt <= M) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        bw.write(Long.toString(left));
        bw.flush();
        bw.close();
        br.close();
    }
}