[백준 2343번] 기타 - java

문제 설명

1. 강의의 수 N, 블루레이 녹화 개수 M이 주어진다.

2. N에 맞추어 강의가 하나씩 주어진다.

3. N개의 강의를 M개로 나누어 저장할 수 있는 가장 최소의 분단위를 구하면 된다.

 

풀이 과정

 1. 이분 탐색 문제이다. 실버1 난이도인데 나는 왜이리 이분탐색이 어려운지 모르겠다...

 2. 중요한 값들에 대해 이야기하자면

      A. N개의 강의를 M개로 나누어 담는다는것 -> 한 개의 블루레이의 크기를 늘리고 줄이며 담을 수 있는 강의를 만들어가면 될것.

      B. 블루레이는 모두 같은 크기를 갖고, 최소의 크기로 만들어야 한다는것 -> 이분탐색을 M개의 값을 갖자마자 나가지 말고 그 최소를 구할것

    이다.

 3. 먼저 M은 N보다 작거나 같으므로 최소 블루레이 크기는 최대 길이 강의로부터 시작할 것이다.

 4. 최대 10000분의 길이를 갖는 강의, 강의의 최대개수 100000 -> 오른쪽 끝 값은 100000*10000 + 1

 5. 왼쪽, 오른쪽 값이 정해졌으므로 그 가운데 mid에 대해 해당 크기에 맞추어 강의를 하나하나 담아준다.

 6. 강의를 담다가 그 크기를 넘어가면 바로 다음 블루레이에 담아준다.

 7. 그렇게 담겨진 블루레이 개수가 M개보다 적으면 블루레이 용량을 키워줘야할것이다. -> mid보다 하나 크게 시작하면 다음 이분탐색

 8. 그렇게 담겨진 블루레이 개수가 M개보다 크면 블루레이 용량을 줄여줘야 할것이다.   -> mid보다 하나 작게 시작하면 다음 이분탐색

 9. 담겨진 블루레이 개수가 M개이면? 더 적은 분단위를 갖는 블루레이가 있을 수 있다 -> mid보다 하나 작게 시작하면 다음 이분탐색

 10. 그렇게 하나하나 나가다보면 왼쪽과 오른쪽이 만나는 지점에 최소의 분단위를 갖는 블루레이를 구할 수 있다.

 11. 그럼 이제... while문을 탈출하고, 왼쪽이나 오른쪽-1이 해당 블루레이의 길이가 될 것이다.

 

코드

	import java.util.*;
	import java.io.*;
	public class Main {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	int num[] = new int[N];
	int max = 0;
	StringTokenizer st2 = new StringTokenizer(br.readLine());
	for(int i=0; i<N; i++){
	num[i] = Integer.parseInt(st2.nextToken());
	max = Math.max(max, num[i]);
	}
	int left = max;
	int right = 100000001;
	while(left <= right){
	int mid = (left+right)/2;
	int sum = 0;
	int cnt = 1;
	for(int i=0; i<N; i++){
	sum += num[i];
	if(sum > mid){
	cnt++;
	sum = num[i];
	}
	}
	if(cnt > M){
	left = mid+1;
	}else{
	right = mid-1;
	}
	}
	// System.out.println(right+1); // 둘다 가능.
	System.out.println(left);
	}
	}

view raw 기타.java hosted with ❤ by GitHub

이분탐색은 뭔가 하나같이 처음에 생각하기 힘든 느낌이다... 더 공부해야 할 것 같다.