[JAVA] 백준 2343 - 기타 레슨

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

2343번: 기타 레슨

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 0;
        int left = Arrays.stream(arr).max().getAsInt(); // 최댓값
        int right = Arrays.stream(arr).sum(); // 합계

        while(left<=right){
            int mid = (left+right) / 2; // 블루레이 한 개의 용량
            if(count(mid) <= m){ // 블루레이 개수가 m보다 작거나 같으면
                answer = mid;
                right = mid - 1; // 블루레이 개수를 늘리기 위해 강의 용량을 줄인다.
            }
            else left = mid + 1;
        }
        System.out.println(answer);
    }

    static int count(int capacity){ // 블루레이 한개의 용량을 capacity로 했을 때 필요한 블루레이의 개수 구하기
        int cnt = 1;
        int sum = 0;

        for(int lecture : arr){
            if(sum + lecture > capacity){ // 강의를 담았을 때 한 블루레이의 용량을 넘어가버리면
                cnt++; // 블루레이 개수 한개 증가
                sum = lecture; // 새로운 값으로 갱신
            }
            else sum+=lecture;
        }
        return cnt; 
    }
}

 

 

문제의 조건대로라면, 가능한 블루레이 크기의 최댓값은

(강의의 수) 최대 10만 X (개당 길이) 1만 = 10억 이 되버린다.

 

그러므로 시간복잡도 O(log n)인 이분 탐색으로 풀어야 한다. 

 

우리가 구하고자 하는 블루레이 한 개의 용량을 mid라고 설정한다.

만약 한 블루레이에 한 강의만 들어가게 된다면, 블루레이 한 개의 용량은 입력받은 강의의 길이 배열중 최댓값인 원소가 된다.

한 블루레이에 모든 강의가 들어가게 된다면, 블루레이 한 개의 용량은 입력 받은 강의의 길이 배열의 모든 원소의 합과 같다.

그러므로 mid의 범위는 left = 배열의 최댓값, right = 배열 원소의 합 으로 설정하고 탐색을 시작한다.

 

이 때, count함수에 mid값(블루레이 한 개의 용량)을 넘겨주어

블루레이 한 개의 용량에 따라 필요한 블루레이의 개수를 구한다.

 

이 값이 m보다 작거나 같으면 블루레이 개수를 늘리기 위해 mid값을 줄이고(블루레이 한 개의 용량이 작아져야 블루레이 개수가 많아지기 때문), m보다 크면 mid값을 늘린다.