기타 레슨 [백준2343][실버 1][이분탐색][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

2343번: 기타 레슨

이분탐색 문제

1. 임의의 블루레이 크기 mid를 정한다.

2. 이분탐색을 시작하여 mid보다 작은 갯수를 구한다.

3. 구한 갯수가 m보다 작다면 최대값을 감소시킨다.

4. 반대의 경우 최솟값을 감소시킨다.

package Study0316;

import java.util.*;

public class 기타레슨 {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        
        int left = 0;
        int right = 0;
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            right += a[i];
            left = left < a[i] ? a[i] : left;
        }
        
        while(left <= right) {
            int mid = (left + right)/2;
            int sum = 0;
            int cnt = 0;
            for(int i=0; i<n; i++) {
                if(sum + a[i] > mid) {
                    sum = 0;
                    cnt++;
                }
                sum += a[i];
            }
            if(sum != 0) cnt++;
            if(cnt <= m) right = mid-1;
            else left = mid+1;
        }
        System.out.println(left);
    }
}