[BOJ] 2343 기타레슨 (Java)

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

 

 

글을 읽으면서 블루레이의 크기를 mid로 두고 조건을 만족하는 경우의 최솟값을 구하면 됨을 알 수 있었다.

조건은 calc 함수를 통해 arr을 순서대로 탐색하며 현재 블루레이 크기 mid인 경우 만들어지는 블루레이 개수 cnt 를 구해 비교해보면 된다.

이때, 블루레이 크기보다 강의의 크기가 커서 담기지 않는 경우를 꼭 고려해주어야 한다.

또한, 블루레이가 다 찬 경우 시작값에 현재 강의 시간을 잘 담아서 다시 계산해주어야 한다.

마지막으로, 블루레이 개수가 꼭 m과 같아야하는 것이 아닌 작을 때도 고려해서 최솟값을 갱신하면 된다!

 

start 값은 1 end 값은 총 강의 시간을 넘어가진 않을 것이므로, 총 강의 시간으로 설정했다.

package BOJ;

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

public class BOJ_2343 {

    static int n, m;
    static int ans = Integer.MAX_VALUE;
    static int[] arr;

    public static boolean calc(int mid){
        int sum = 0;
        int cnt = 1;
        for(int i=0; i<n; i++){
            // 블루레이보다 한 강의의 크기가 커서 담기지 않는 경우
            if(arr[i] > mid) return true;
            // 블루레이가 다 찬 경우
            if(sum + arr[i] > mid) {
                cnt++;
                sum = arr[i];
            }else sum += arr[i];
        }
        // 블루레이 개수가 더 큰 경우
        if(cnt > m) return true;
        else {
            ans = Math.min(ans, mid);
            return false;
        }
    }

    public static void binarySearch(int s, int e, int m){
        if(s > e) return;
        int mid = (s + e) / 2;
        if(calc(mid)) binarySearch(mid+1, e, m);
        else binarySearch(s, mid-1, m);
    }

    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];
        int end = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            end += arr[i];      // 총 강의 길이가 maximum
        }
        binarySearch(1, end, m);
        System.out.println(ans);
    }
}