자바(백준) 2343 기타 레슨

오답 노트 & 새로 알게 된 점

해당 문제는 매개 변수 탐색 방법을 사용하여 풀었다.

possible 메서드 안에서 어떻게 반환할지 매우 헷갈렸다.

cnt <= M 인지, cnt >= M인지 말이다.

 

이렇게 생각하면 될 것 같다.

target 즉, 블루레이의 크기가 커질수록 cnt가 작아진다.

우리가 구하고 싶은 것은 크기의 최솟값이다. true인 것들 중에 가장 왼쪽 값이다.

그래서 cnt가 작을 때 true을 반환한다는 것은 블루레이의 크기가 일정 이상이면 모두 true이고,

거기서 가장 작은 값을 구하는 것이다.

 

실수했던 부분은 정렬을 하면 안된다. 왜냐하면 문제에서 강의를 순서대로 넣는다고 했기 때문이다.

 

---

코드

package Binary_Search;
 
import java.io.*;
import java.util.*;
 
public class BOJ2343 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static int N; //강의 수
    static int M; //블루레이 개수
    static int a[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        a = new int[N];
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < N; i++) {
            a[i] = atoi(st.nextToken());
        }
 
//        Arrays.sort(a);
        paraSearch();
 
    }
 
    //target은 블루레이 크기
    static boolean possible(int target) {
        int cnt = 1, sum = 0;
 
        for (int i = 0; i < N; i++) {
            sum += a[i];
            if(sum > target){
                cnt++;
                sum = a[i];
            }
        }
        return cnt <= M;
        //cnt가 M보다 작거나 같다 -> 블루레이 크기가 크다\
        //-> 그것들 중에 제일 왼쪽 값
    }
 
    static void paraSearch() {
        int s = 0, e = 1000000000, rel = 0;
 
        for (int i = 0; i < N; i++) s = Math.max(s, a[i]);
        while (s <= e) {
            int mid = (s + e) / 2;
 
            if (possible(mid)) {
                rel = mid;
                e = mid - 1;
            }
            else s = mid + 1;
        }
        System.out.println(rel);
    }
}
/**
 * M개의 블루레이에 담을 때, 블루레이의 최소 크기?
 * -> 블루레의의 크기가 S 일 때, M개의 블루레이를 만족하냐?
 */