[백준] 2343 기타 레슨- Java

 

 

 

매개변수 탐색을 통해 풀 수 있는 문제이다.

 

이분탐색을 수행할 때 최솟값을 구하는 경우이므로 최댓값을 구하는 경우와 헷갈리지 말자.

 

 

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

public class Main {

	static int N;
	static int M;

	static int[] lecture;

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

		lecture = new int[N+1];

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

		for(int i=1; i<N+1; i++){
			lecture[i] = Integer.parseInt(st.nextToken());
		}

		//Arrays.sort(lecture, 1, N+1);

		System.out.println(ParameterSearch());



		
	}

	static boolean check(int len){
		int cnt = 1;
		int sum = 0;

		for(int i = 1; i<N+1; i++){
			if(sum + lecture[i] > len){
				cnt++;
				sum = lecture[i];
			}else{
				sum = sum + lecture[i];
			}
		}

		if(cnt <= M){
			return true;
		}else{
			return false;
		}
	}

	static int ParameterSearch(){
			int L = 0;
			int R = 1_000_000_000;
			
			for (int i = 1; i <= N; i++){
				L = Math.max(L, lecture[i]); 
			}
			//int R = Integer.MAX_VALUE;
			int ans = 0;			


			while(L <= R){
				int mid = (L + R) / 2;

				if(check(mid)){
					ans = mid;
					R = mid - 1;
				}else{
					L = mid + 1; // 최소찾는거니까.. 최대랑은 반대로.
				}
			}

			return ans;

			
	}

}