백준 2343번 : 기타 레슨 [Java]

문제

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

2343번: 기타 레슨

 

코드

package baekjoon;

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

public class Main_2343 {

	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[] lectureTime = new int[N];
		st = new StringTokenizer(br.readLine());
		int minTime = Integer.MIN_VALUE, maxTime = 0;
		for(int i = 0; i < N; i++) {
			lectureTime[i] = Integer.parseInt(st.nextToken());
			minTime = Math.max(minTime, lectureTime[i]);
			maxTime += lectureTime[i];
		}
		int answer = 0;
		while(minTime <= maxTime) {
			int blurayTime = (minTime + maxTime) / 2;
			int sum = 0;
			int blurayCount = 0;
			for(int time : lectureTime) {
				if(sum + time > blurayTime) {
					blurayCount++;
					sum = 0;
				}
				sum += time; 
			}
			if(sum != 0) blurayCount++;
			if(blurayCount <= M) {
				maxTime = blurayTime - 1;
			}
			else {
				minTime = blurayTime + 1;
			}
		}
		System.out.println(minTime);
	}

}

 

접근 방법

우선 이 문제를 읽고 이진 탐색이라는걸 떠올리는게 너무 어려웠다.

블루레이는 순서가 바뀌면 안되기 때문에 새로 정렬을 한다든가 하는 일은 불가능하다.

따라서 만들 수 있는 블루레이의 최소값과 최대값을 정해놓고 이진탐색을 해서 만들 수 있는 최소값을 찾아야했다.

 

최소값은 강의 시간 중 가장 긴 것이 될 수 있고

최대값은 모든 강의를 하나의 블루레이에 넣는경우 즉, 모든 강의시간의 합이 될 수 있다.

이렇게 최소 최대값을 정해놓고 이진탐색을 하며 가운데 값으로 만들 수 있는 블루레이가 몇개인지 센다.

 

만들어지는 블루레이가 M보다 작으면 최대값의 범위를 가운데 값보다 1작게 (=더 작게 쪼갤 수 있다는 뜻이니까)

M보다 크면 최소값의 범위를 가운데 값보다 1크게 (=더 크게 쪼개야한다는 의미니까)

 

이렇게 하다보면 최소값이 정답이 된다.