[백준 c++] 2343 기타 레슨

문제

https://www.acmicpc.net/problem/2343
N개의 강의를 M개의 블루레이에 녹화하려고 할 때 가능한 블루레이의 크기 중 최소를 구하는 문제

풀이

특정 값을 찾는 거니까 이분탐색을 이용해서 풀 수 있다.
여기서 left, right값을 설정할 때 주의해야한다.
동영상은 잘라서 담을 수 없기 때문에 블루레이 길이 최소값left는 1이 아니라 가장 긴 강의의 길이다.
또한 블루레이 길이 최대값 right는 모든 강의 길이 총합이다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, a[100001], hi, lo, res;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        hi += a[i];
        lo = max(lo, a[i]);
    }
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        int cnt = 1, sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (sum + a[i] <= mid)
                sum += a[i];
            else
            {
                cnt++;
                sum = a[i];
            }
        }
        if (cnt <= m)
        {
            hi = mid - 1;
            res = mid;
        }
        else
            lo = mid + 1;
    }
    cout << res << "\n";

    return 0;
}