[2343] 기타 레슨 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M; cin >> N >> M;
    vector<int> A(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int min = *max_element(A.begin(), A.end());
    int max = accumulate(A.begin(), A.end(), 0);

    while (min <= max) {
        int mid = (min + max) / 2;
        int sum = 0, 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) min = mid + 1;
        else max = mid - 1;
    }
    
    cout << min;
    return 0;
}

 

1. 만약 M = 1일때 블루레이에 모든 영상이 담겨야 하므로, 블루레이에 담길 수 있는 영상의 최대 길이는 모든 영상의 합

2. 블루레이에 담기는 영상의 최소 길이는 가장 긴 영상의 길이와 같다 (M = N)

3. 강의의 수가 100,000이며 M = N의 경우를 가정할 때의 풀이를 위해 이분 탐색을 사용해야 한다

4. 블루레이에 담기는 영상의 최소 길이부터 최대 길이까지 탐색

=> 이 때 이분 탐색을 사용해 영상의 길이 중간을 지정해 이분 탐색을 사용