[JAVA]백준 2343: 기타 레슨

백준 2343: 기타 레슨

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

풀이

• 이분탐색이 너무 머리에 안들어와서 분류를 알고 푼 문제
• N개의 강의를 M개의 블루레이에 담아야 함.
• 블루레이의 크기를 최소로 해야 한다. 단, 블루레이 M개는 모두 같은 크기
• 블루레이의 크기를 이분탐색으로 탐색
• Lower Bound를 이용하여 블루레이 M개에 모두 담을 수 있는 경우 중 가장 작은 값 구하기

package algorithm2024.jan.day03;

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

public class BOJ_2343_기타레슨 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, M, lecture[];
    public static void main(String[] args) throws Exception{
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lecture = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            lecture[i] = Integer.parseInt(st.nextToken());
        }
        int lo = 1;
        int hi = N*10000+1;
        while(lo<hi){
            int mid = (lo + hi) / 2;
            int sum = 0;
            int cnt = 1;
            boolean isBig = false;
            for (int i : lecture) {
                if(i>mid){
                    isBig = true;
                    break;
                }
                sum+=i;
                if(sum>mid){
                    cnt++;
                    sum=i;
                }
            }
            if(cnt>M||isBig){
                lo = mid+1;
            }else{
                hi = mid;
            }
        }
        sb.append(hi);
        System.out.println(sb);
    }
}

---

Issue

• 이분탐색은 왜 이리 어려울까