2343_기타 레슨 (JAVA)

2343번: 기타 레슨

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] lesson;

	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt(); M = sc.nextInt();
    	lesson = new int[N];

    	int total = 0; int max1 = 0;
    	for(int i=0; i<N; i++){
    		lesson[i] = sc.nextInt();

    		/*
            right=total == 블루레이 하나 크기가 total
			이 경우 블루레이 1개에 모두 담을 수 있음 (최대값)
            */
            total += lesson[i];
    		
            
    		/*
            left=max1 == 블루레이 하나 크기가 lesson의 max값
			max값이 아닌 경우에는 블루레이에 담을 수 없는 값들이 존재하게됨. 
            그러므로 최소값
            */
            max1 = Math.max(max1, lesson[i]);
		}

    	int cnt = 0; //개수 --> M이 되어야함
		int sum = 0; //lesson[i] 더해서 블루레이크기랑 비교할 값

    	int left = max1;
    	int right = total;
    	int mid = 0;

    	while(left <= right){
    		/*
            "무엇을 찾을 것인가?" - 찾을 값은 3개로 나누어지는 블루레이 크기값
			예) 블루레이 크기가 11이라면 - 1234, 56, 7, 8, 9 로 5개로 나누어짐 (X)
			찾을 값 = mid 로 놓고, 개수 많으면 블루레이 크기값을 늘리고
            개수 적으면 블루레이 크기값을 줄이고..
            */

			cnt = 0; sum = 0;
			mid = (left+right)/2;

			for(int i=0; i<N; i++){
    			sum += lesson[i];

    			if(sum > mid){
    				sum = lesson[i];
    				cnt++;
				}
			}

			if(sum != 0) cnt++;

    		if(cnt > M){ //개수 많으면 - 블루레이 크기 늘리고
    			left = mid+1;
			}
    		else if(cnt <= M){ //개수 적으면 - 블루레이 크기 줄이고
    			right = mid-1;
			}
		}
    	System.out.println(left);
    }
}

 

처음 풀어보는 이분탐색 문제! 이분탐색 개념은 알았는데, 이거를 문제에 어떻게 활용할지 감이 잡히지 않아서 오래걸렸다..! 익숙해져야지

 

[문제 풀이 생각 과정]

1. "문제의 크기를 정확히 양분하는 경우" "주어진 자료에서 특정값을 찾을 때"

---- 이런 경우 이분탐색으로 문제를 푼다고 한다.

2. 이분탐색에서 포인트는 "무엇을 찾을 것인가"  +  찾는 값의 범위 선정

    1) 우리가 찾을 값은 : 블루레이의 최대 크기

    2) 찾는 값의 범위 : 최소값(left)은 최대 lesson[i]값!

         - 왜냐면, lesson={1,2,3,4,5,6,7,8,9}일때 블루레이의 크기가 1이라면, 1만 블루레이에 들어갈 수 있다.

         나머지 2~9는 넣을 수 없으므로 안됨!

         최소 9가 되어야 1~9의 모든 값을 블루레이에 넣을 수 있다.

         최대값(right)은 모든 lesson[i]을 합한 값!

         - 왜냐면, 블루레이의 크기가 1+2+3+4+5+6+7+8+9=45 라면, 블루레이 1개에 모든 값이 들어갈 수 있다.

            최소 1개의 블루레이가 필요하기 때문에, 범위의 최대값은 모든 lesson[i]를 합한 값이다.

3. mid = 블루레이의 크기 로 놓고, 블루레이의 개수가 M보다 많으면 - 블루레이의 크기를 늘린다.  : left = mid+1;

    예) lesson={1,2,3,4,5,6,7,8,9} 일때, mid=11이라면

          {1,2,3,4},{5,6},{7},{8},{9} 로 블루레이 개수는 5가 된다. 

          mid=15라면 {1,2,3,4,5},{6,7},{8},{9} 로 블루레이 개수는 4이 된다.

          그러므로 블루레이 개수를 줄이려면 블루레이 크기(mid)를 늘려야한다.

    반대로, 블루레이의 개수가 M보다 같거나 적으면 - 블루레이의 크기를 줄인다.  : right = mid-1;

4. 정답은 left를 출력한다.

    mid 범위상으로는 left는 범위의 최소값이지만,

    블루레이 개수가 M일 때의 최대 블루레이 크기이므로 정답!