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

isaacToast 2020. 3. 17. 23:59

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

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

2343번: 기타 레슨

강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가

www.acmicpc.net

이분탐색 문제

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);
    }
}