2343_기타 레슨

사용 알고리즘: 이분탐색

사용 언어: java

 

package di_5_3_이진탐색;

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

public class Main_bj_2343_기타레슨 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		int m = sc.nextInt();
		
		int right = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
			right += arr[i];
		}
		
		//
		int left = 1;
		int answer = -1;
		while(left <= right) {
			int mid = (left + right) / 2;
			//블루레이 크기가 mid일 때, 구간이 몇 개 나오나
			
			if(solve(mid, arr) <= m) {
				right = mid - 1;
				answer = mid;
			} else {
				left = mid + 1;
			}
		}
		
		System.out.println(answer);
	}

	private static int solve(int size, int[] arr) {
		int bluelay = 1;
		//크기(size)에 따라, 블루레이의 개수 구하기
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			
            //아래 코드를 추가하지 않으면 50%에서 끝났음...
			if(arr[i] > size)
				return Integer.MAX_VALUE;
            ///
			sum += arr[i];
			if(sum > size) {
				bluelay ++;
				sum = arr[i];
			}
		}
		
		return bluelay;
	}

}

 

 

전형적인 파라메트릭 이분탐색!!

틀린 이유가 뭔지 질문 게시판을 찾아보았다.

아래는 찾은 반례.

7 7
5 9 6 8 7 7 5

 

주석으로 감싸진 코드를 빼면, 답이 5가 나온다. 실제 답은 9인데...

 

블루레이의 사이즈가 5라고 쳤을 때, 5를 초과하는 곡이 있다면 실패해야 하는데,

원래 코드에서는 계속 블루레이의 개수만 더해간다.

 

그래서 주석 코드를 추가하여, 블루레이를 만들 수 없는 사이즈일 때는 최대값을 리턴하게 하였다.