[백준] 2343번. 기타레슨(JAVA)

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

---

문제

---

풀이

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

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] time = new int[n];
        long start = 0;
        long end = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            time[i] = Integer.parseInt(st.nextToken());
            if(start < time[i]) start = time[i];
            end += time[i];
        }



        while (start <= end){
            long mid = (start + end) / 2;
            long sum = 0;
            int count = 0;

            for(int x : time){
                if(sum + x > mid){
                    count ++;
                    sum = 0;
                }
                sum += x;
            }
            if(sum != 0) count++;
            if(count <= m){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }
        System.out.println(start);
    }

}

 

시작 지점은 영상 길이 중 최소로 잡고, 종료 지점은 모든 영상 길이의 합으로 설정한다.

이후 이분탐색을 진행하며 만약 연속된 영상의 길이가 중간값을 넘는다면 블루레이 개수를 ++ 하고 초기화한뒤 나온다.

이 블루레이 개수가 제시된 개수보다 적거나 같다면 중간값을 낮추고, 아니라면 올리는 방식으로 진행한다.