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

문제

접근 방법

순서가 바뀌면 안 된다는 점에서 정렬은 배제된다.
그렇다면 순서를 유지하면서 해당하는 값이 맞는지 확인해 줘야 한다.

1부터 가능한 모든 수를 확인하는 방법은 너무 많은 경우를 확인해 준다.
이분 탐색을 활용해 주면 큰 범위의 탐색을 빠르게 해줄 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, low, high;
vector<int> videos;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;

    videos = vector<int>(N);
    for (int &video : videos)
    {
        cin >> video;
        low = max(low, video);
    }
}
int solve()
{
    int mid, size, cnt, answer;
    answer = 0;
    high = 1000000000;

    while (low <= high)
    {
        mid = (low + high) >> 1;
        size = 0;
        cnt = 1;

        for (const int &video : videos)
        {
            size += video;
            if (size > mid) // 크기를 넘어가면
            {
                ++cnt;
                size = video;
            }
        }

        if (cnt <= M) // 해당 값만큼 크기를 설정해도 개수가 많거나 같다면
        {
            high = mid - 1;
            answer = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    return answer;
}
int main()
{
    input();
    cout << solve();
    return 0;
}

풀이

블루레이의 최대 크기를 이분 탐색으로 구해주는 것이다.
만약 해당 최대 크기로 블루레이를 나누었는데 개수가 적다면 최대 크기를 너무 크게 했다는 의미이니 크기를 줄이고 개수가 많다면 너무 적게 했다는 뜻이므로 크기를 늘리면 된다.

조심해야 할 점은 블루레이의 최대 크기가 동영상의 최대 크기보다 작은 경우이다.
그러한 경우가 존재할 순 없으므로 시작점을 가장 큰 동영상의 크기로 해주는 것이 좋다.