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

2343번: 기타 레슨

 

이분탐색으로 문제를 해결할 수 있다.

 

이분탐색을 진행하면서 중간값(mid)이 블루레이 최소 크기의 후보가 된다.

각 레슨의 길이가 저장된 배열을 차례대로 탐색하여 한 블루레이당 레슨 길이의 합이 mid보다 작도록 레슨을 그룹으로 분리한다.

 

예를 들어, mid = 15 이고, 레슨의 길이가 차례대로 1 2 3 4 5 6 7 8 9 이면, 한 블루레이당 레슨 길이의 합이 mid보다 작도록 나누면 (1,2,3,4), (5,6), (7), (8), (9) 로 나눌 수 있다.

각각의 블루레이 레슨의 길이의 합은 10, 11, 7, 8, 9가 되어 mid인 15를 넘지 않는다. 

 

- 만약 이렇게 레슨을 분리한 그룹의 수가 M보다 크다면(즉, 총 필요한 블루레이 개수가 M보다 크다면)

   left = mid + 1 로 변경하고,

 

- 레슨을 분리한 그룹의 수가 M보다 작거나 같다면 right = mid - 1로 변경해준다.

 

 

소스코드 : 

	import java.io.*;
	public class n02343 {
	static int N, M;
	static int[] lesson;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] sarr = br.readLine().split(" ");
	N = Integer.parseInt(sarr[0]);
	M = Integer.parseInt(sarr[1]);
	lesson = new int[N];
	int max = 0;
	sarr = br.readLine().split(" ");
	for (int i = 0; i < N; i++) {
	lesson[i] = Integer.parseInt(sarr[i]);
	max = Math.max(max, lesson[i]);
	}
	bw.write(binSearch(max, 1000000000) + "\n");
	bw.flush();
	}
	public static int binSearch(int left, int right) {
	int pl = left;
	int pr = right;
	do {
	int pc = (pl + pr) / 2;
	int cnt = 1;
	int sum = 0;
	for (int i = 0; i < N; i++) {
	sum += lesson[i];
	if (sum > pc) {
	sum = lesson[i];
	cnt++;
	}
	}
	if (cnt > M)
	pl = pc + 1;
	else
	pr = pc - 1;
	} while (pl <= pr);
	return pl;
	}
	}

view raw 2343.java hosted with ❤ by GitHub