[BOJ] 백준 2343 기타 레슨

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

2343번: 기타 레슨

 

---

 

풀이 방법

블루레이의 크기를 임의의 값인 10으로 설정한 과정

• 우선 블루레이의 크기를 임의의 값인 10으로 두고 계산을 하면, 레슨의 순서가 바뀌면 안 되는 조건이 있기 때문에 1+2+3+4를 더해서 한 개, 5+6을 한다면 10보다 커지므로, 뒷부분은 더할 수 있는 값이 없다. 결과적으로 블루레이의 수는 6개가 나온다.
• m이 3이고 블루레이의 수는 6이기 때문에 블루레이의 크기를 늘려야 된다는 것을 알 수 있다.
• 그러면 low와 high는 어떻게 정해야 할지 생각해 보자. low부터 보면 레슨의 길이는 자연수라고 명시가 되어 있으므로, low는 0이 될 수 없다. 만약, 가장 작은 레슨의 길이인 1로 둔다면, 길이가 1인 레슨만 담을 수 있으므로 길이가 가장 긴 9로 설정한다.
• high는 각 레슨의 길이를 모두 더한 값으로 설정한 후, 이분 탐색을 돌린다.
• 반복문을 돌려서 레슨의 길이를 더하는데, 더한 값이 low와 high의 중간값인 mid보다 클 경우, count를 하나 올려준다.
• 더한 값이 mid 값보다 작아, 집계가 되지 않을 경우를 대비해서 if문으로 처리를 한다.
• count가 정해진 블루레이의 수인 m보다 크다면, low를 늘리고 같거나 작다면 high를 줄인다.

 

다음은 Java로 작성한 코드이다.

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

public class B2343 {
    private static int n, m;
    private static int [] arr;
    private static int low, high;

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

        arr = new int[n];

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

        int sum = 0;

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
            low = Math.max(low, arr[i]);
        }

        high = sum;

        binarySearch();

        System.out.println(low);
    }

    private static void binarySearch() {
        int mid, sum, count;

        while (low <= high) {
            mid = low + high >> 1;
            sum = 0;
            count = 0;

            for (int i = 0; i < n; i++) {
                if (sum + arr[i] > mid) {
                    sum = 0;
                    count++;
                }

                sum += arr[i];
            }

            if (sum > 0) count++;

            if (count <= m) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }
}