[BOJ 2343] 기타 레슨 (Java, 매개변수 탐색)

 

 

 

---

문제 링크

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

2343번: 기타 레슨

---

풀이

- 이진탐색 (매개변수 탐색) 으로 풀이하면 되는 문제 

- 시간 복잡도는 O(NlogN)

 

범위 지정시 (L, R) 

L 의 경우 100,000개의 강의(N)를 100,000 개의 블루레이(M)에 담는다 할 때 (각 강의 길이 또한 최대 10,000분)

최소 10,000분이 되야함. 10,000분 이하는 담을 수가 없기 때문에, 최소 10,000분이 기준이 됨 

L 은 고로 주어진 배열에서 가장 큰 값이 기준이 됨

R 은 전체 강의 길이 합에 해당함. (블루레이 1개에 전체 강의를 담을 때를 생각)

 

L, R 범위 지정을 생각못해서 시간 소비

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, M, MIN, MAX;
    static int[] A;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            MIN = Math.max(MIN, A[i]);
            MAX += A[i];
        }
    }

    static boolean isValid(int range) {
        int cnt = 0;
        int sum = 0;

        for(int a : A) {
            if(sum + a > range) {
                cnt += 1;
                sum = 0;
            }

            sum += a;
        }

        if(sum > 0) cnt += 1;

        return cnt <= M;
    }

    static void pro() {
        int L = MIN, R = MAX, ans = 0;
        while(L <= R) {
            int mid = (L + R) / 2;

            if(isValid(mid)) { // 조건 성립하는 최소값을 찾으므로, R을 줄여감
                R = mid - 1;
                ans = mid;
            } else {
                L = mid + 1;
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}