[BaekJoon] 2343 기타 레슨

1.  문제 링크

2.  문제

요약

• N개의 기타 강의가 블루레이에 들어가는데 블루레이에 강의가 들어갈 때 강의의 순서가 바뀌지 않도록 합니다.
• M개의 블루레이에 모든 기타 강의 동영상을 녹화하는데, M개의 블루레이는 모두 같은 크기이어야 하며 블루레이의 크기를 최소로 합니다.
• N과 M이 주어질 때 최소로 하는 블루레이의 크기를 구하는 문제입니다.
• 입력: 첫 번째 줄에는 기타 강의의 개수 N과 블루레이의 개수 M이 주어지고 두 번째 줄에는 강의 순서대로 N개의 기타 강의의 길이가 주어집니다.
• 출력: 최소로 하는 불루레이의 크기를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public int getMinSize(int bluray_num, int[] class_min) {
		int left = 0;
		int right = 0;
		for(int i = 0; i < class_min.length; i++) {
			right += class_min[i];
			left = Math.max(left, class_min[i]);
		}
		while(left <= right) {
			int count = 0;
			int sum = 0;
			int middle = (left + right) / 2;
			for(int i = 0; i < class_min.length; i++) {
				sum += class_min[i];
				if(sum > middle) {
					sum = class_min[i];
					count++;
				}
			}
			if(sum != 0) {
				count++;
			}
			if(count > bluray_num) {
				left = middle + 1;
			} else {
				right = middle - 1;
			}
		}
		return left;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int class_num = Integer.parseInt(st.nextToken());
		int bluray_num = Integer.parseInt(st.nextToken());
		int[] class_min = new int[class_num];
		input = br.readLine();
		br.close();
		st = new StringTokenizer(input);
		for(int i = 0; i < class_min.length; i++) {
			class_min[i] = Integer.parseInt(st.nextToken());
		}
		Main m = new Main();
		bw.write(m.getMinSize(bluray_num, class_min) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 이분 탐색을 이용하여 구하는 문제입니다.

1. 주어진 강의 길이 중에서 가장 큰 값을 left라는 변수에 넣고 주어진 강의 길이를 모두 더한 값을 right라는 변수에 넣습니다.
2. left 값이 right 값보다 커질 때까지 반복문을 돌립니다.
1. middle이라는 변수에 (left + right) / 2의 값을 넣습니다.
2. 주어진 강의 길이들을 돌면서 sum이라는 변수에 주어진 강의 길이들을 더해갑니다.
3. 만약 middle이라는 변수값보다 sum의 변수값이 크다면 sum의 변수값을 현재 강의 길이로 변경하고 count라는 변수의 값을 1 올립니다.
4. 주어진 강의 길이들을 모두 돌았을 때, 아직 sum 변수값이 0이 아니라면 count 값을 1 늘려줍니다.
5. 만약 count 값이 주어진 블루레이 개수 M보다 크다면 left 변수에 middle 변수값에 1을 추가한 값을 넣고 그렇지 않다면 right 변수에 middle 변수값에 1을 뺀 값을 넣습니다.
3. 위 반복문을 통해 구한 left 변수값이 최종 결과값이 됩니다.

• 위 과정에서 middle을 블루레이의 크기, count는 middle이라는 블루레이 크기에서 구해지는 블루레이의 개수라고 바라볼 수 있습니다.
• count 값이 주어진 블루레이 개수보다 클 때는 주어진 블루레이 개수보다 middle이라는 블루레이 크기에서 더 많은 블루레이를 필요로 하기 때문에 블루레이 크기를 늘려 블루레이 개수를 줄이려고 한다고 생각할 수 있습니다.
• 반대로 count 값이 주어진 블루레이 개수보다 작을 때는 주어진 블루레이 개수보다 middle이라는 블루레이 크기에서 더 적은 블루레이를 필요로 하기 때문에 블루레이 크기를 줄여 블루레이 개수를 늘리려고 한다고 생각할 수 있습니다.
• count 값이 주어진 블루레이 개수와 같은 경우에는 이 문제는 최소의 블루레이 크기를 구하는 문제이기 때문에 최소의 블루레이 크기를 찾기 위해 블루레이 크기를 줄여나간다라고 생각할 수 있습니다.