[백준/Java] 2343 기타 레슨

조건

1. 총 강의의 수 N개 주어진다. (1<= N <= 100,000 , int)

2. 블루레이의 수 M개 (1<= M <= N , int)

3. 블루레이의 크기를 최소해야한다 -> 정해진 개수로 최소한의 분으로 녹화가 가능한 분을 출력하라

예제 입력

코드

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



public class Main {
	
	static int N,M;
	static int A[];
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
	
		N = scan.nextInt(); // 강의 개수를 받는다.
		M = scan.nextInt(); // 블루레이의 개수를 받는다.
		A = new int[N + 1]; // index를 1부터 시작하기 위해 + 1을 해준다.
		for(int i=1;i<=N;i++) {
			A[i] = scan.nextInt();
		}
	}

	
	static boolean findAns(int length) {
	int cnt = 1 , sum =0;
	for(int i = 1;i<=N ; i++) {
		if(sum + A[i] > length) {
			cnt++; // legth 길이보다 커지면 다음 블루레이를 사용하기 위해 ++을 해주고
			sum = A[i]; // sum = A[i]를 넣어준다
		}else {
			sum +=A[i];
		}
	}
	return cnt<=M; // 주어진 블루레이 개수 이하면 return을 해준다.
	}
	

	static void find() {
		int L =A[1], R = 100000000, ans =0; // L은 강의 첫 시간을 넣어주고 
        									// R은 int형 최대 수를 넣어준다.
		for(int i= 1;i<=N;i++) L = Math.max(L, A[i]); // 제일 긴 녹화 길이는 해야하기 때문에 max로 최대값을 찾아준다.
		
		while(L<=R) {
			int mid = (L + R ) / 2;
			if(findAns(mid)) {
				ans = mid;
				R = mid -1;
			}else {
				L = mid +1 ;
			}
		}
		System.out.println(ans);
		}

		
		
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}