백준 2343번 자바 ☆

문제

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

1. 접근방식

이전에 풀었던 문제와 마찬가지로 이분탐색으로 접근해야 한다. 다만 문제에 대한 이해도가 떨어져 이분탐색할 범위를 이상하게 잡아 문제 해결에 어려움을 겪었다.

 

먼저, 블루레이 최소크기가 9이고 최대크기가 45임을 이해해야한다. 

최소크기가 9인 이유는 나열된 강의들 중 가장 긴 강의가 9길이의 영상이기 때문이다.

즉, 각 개별의 영상크기가 가장 마지막 영상의 길이인 9보다 작기 때문이다.

 

최대크기가 45인 이유는 모든 강의를 담았을 때 총 길이가 45이기 때문이다.

9~45의 수가 정렬이 되어 있으므로 이분탐색을 통해 블루레이가 3개일 때  최소크기의 블루레이를 찾는다.

 

count의 값이 곧 블루레이의 갯수다.

count의 값이 기준이 되는 M보다 크다면 start의 값을 중간값 +1로 한다.

예를 들어 15로 담을 수 있는 블루레이 개수가 4개라면 16이상의 값에선 3개가 될 수도 있기 때문이다.

 

반대로 count의 값이 M보다 작거나 같다면 end의 값을 중간값 -1로 한다.

반복문이 끝나고난 start의 값이 정답이 된다.

2. 구현

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

public class Main {

	static int N,M;
	static int[] courses;
	static int start;
	static int end;
	
	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());
		courses = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			courses[i] = Integer.parseInt(st.nextToken());
		}
		for (int i=0; i<N; i++) {
			if (start < courses[i]) {
				start = courses[i];
			}
			end += courses[i];
		}
		while (start <= end) {
			int mid = (start+end)/2;
			int sum = 0;
			int count = 0;
			for (int i=0; i<N; i++) {
				if (sum + courses[i] > mid) {
					count++;
					sum = 0;
				}
				sum += courses[i];
			}
			if (sum != 0) {
				count++;
			}
			if (count > M) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}	
		System.out.println(start);	
	}
}