😐 뮤직비디오

😀 문제

😀 풀이

😲 어떻게 풀까?

• 이분검색을 할 조건은 내가 정한 범위 내에서 확실히 정답이 있을 경우에 사용을 하자.

• 1장에 담을 수 있는 최솟값 과 최댓값을 각각 lt, rt 라고 하자.

• mid = (lt+rt)/2; 라 하자.

• 입력 값이 위와 같이

9 3
1 2 3 4 5 6 7 8 9

일 경우에, mid= 27이 된다.

• DVD용량이 27일 경우에, 3개로 위의 데이터를 담을 수 있을까를 생각해보자.

• 1+2+3+4+5+6+7= 28 이므로 7까지는 담을 수 없다.

• 1+2+3+4+5+6 = 21이므로 6까지 담을 수 있다.

• 7+8+9 = 24 이므로 담을 수 있다.

즉, DVD용량을 27로 설정했을 경우, DVD2개로 위의 Data를 담을 수 있다는 얘기가 된다.

2개로 위의 용량을 다 담을 수 있으므로, 3장으로도 가능하다.

😲 버려야할 부분을 선택해보자.

1번일까, 2번일까..

답은 2번이다. 그 이유는 DVD 1개의 용량이 27일때 3개를 담을 수 있다면, 27보다 큰 용량을 사용해서도 당연히 담을 수 있다는 것이다.
우리는 DVD 1개의 최소 용량을 구하는 것이므로, 2번 부분을 버리도록 하자.
즉 rt = mid-1 을 해주도록 하자.

다시 입력 값을 보자

9 3
1 2 3 4 5 6 7 8 9

• 1+2+3+4+5 = 15
• 6+7 = 13
• 8+9 = 17

위의 사실을 토대로 DVD 1개의 용량이 17일 때에도 성립이 된다.

다시 입력값을 보자

9 3
1 2 3 4 5 6 7 8 9

• 1+2+3+4 = 10
• 5+6 = 11
• 7+8 = 15 (X)

따라서 12는 답이 될 수 없다.

lt = mid+1 을 해주자.

위와 같은 방법을 반복하면 우리가 원하는 답을 구할 수 있을 것이다.

😀 소스코드

package algolecture;
import java.util.Arrays;
import java.util.Scanner;

public class Main51 {
    public int count(int[] arr, int capacity){
        int cnt=1, sum =0;
        for(int x : arr){
            if(sum+x>capacity){
                cnt++;
                sum=x;
            }
            else sum+= x;
        }
        return cnt;
    }

    public int solution(int n, int m, int[] arr){
        int answer = 0;
        // 간단하게 최대값을 구해주는것.
        // stream클래스에 있는 메소드 max
        // 큰 데이터에서 최댓값을 찾을 때 stream을 사용하자!
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).sum();

        while(lt <= rt){
            int mid = (lt+rt)/2;
            if(count(arr, mid) <= m){
                answer = mid;
                rt = mid -1;
            }
            else
                lt = mid+1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main51 T = new Main51();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = kb.nextInt();
        System.out.println(T.solution(n,m,arr));
    }
}