[백준] 2343번 - 기타레슨

문제

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

2343번: 기타 레슨

 

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

 

사고의 흐름

우선 블루레이의 크기를 생각해본다.

늘 그랬듯이 하나씩 탐색해보는 완전탐색을 생각해보자.

 

강의의수는 최대 100,000개이고, 블루레이 갯수도 최대 100,000개가 될 수 있다.

코드로 생각해보면

 

블루레이 갯수 1 ~ 100,000개

강의의수 100,000개를 다 돌면서 정해진 블루레이 갯수만큼 나누고, 나눈 값의 합의 제일 큰것들을 비교

 

시간복잡도가 100,000 * 100,000개가 된다.

 

어떻게 시간 복잡도를 줄일까..?

 

N을 logN으로 줄이는 이분탐색을 사용해보자

이분탐색의 탐색 조건은 정답을 찾으면 된다. 블루레이 크기중 최소가 되는 것

 

주어진 값을 전부다 합한 값을 최댓값으로 두고,

이진탐색을 하면서 블루레이 크기의 최소를 찾는다.

 

풀이 코드

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

public class Main {

    public static int N;
    public static int M;
    public static int low;
    public static int high;
    public static int ret;

    public static int[] arr;
    public static int sum;
    public static int mx;

    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());

        st = new StringTokenizer(br.readLine());

        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
            mx = Math.max(mx, arr[i]);
        }

        // 블루레이를 몇개씩 가져가야 할까?
        low = 0;
        high = sum;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (check(mid)) {
                high = mid - 1;
                ret = mid;
            } else {
                low = mid + 1;
            }
        }

        System.out.println(ret);
    }

    public static boolean check(int mid) {
        if (mx > mid) {
            return false;
        }

        int temp = mid;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (mid - arr[i] < 0) {
                mid = temp;
                cnt++;
            }

            mid -= arr[i];
        }

        if (mid != temp) {
            cnt++;
        }

        return cnt <= M;
    }
}