숫자구슬 2613

문제

접근 방법

적절한 값을 찾아서 나눠주는 것이 중요하다.
그 적절한 값은 이분 탐색으로 구할 수 있다.

만약 특정 값을 기준으로 범위를 나누었을 때 M보다 많이 나누어진다면 값을 올리고 낮거나 같으면 값을 내리면 된다. (최소인 최댓값이므로)

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int N, M;
void print(int target)
{
    cout << target << "\n";
    int i = 0, cnt = 1, smallCnt = 0, sum = 0;
    for (; i < N; ++i)
    {
        if (sum + v[i] <= target)
        {
            sum += v[i];
            ++smallCnt;
        }
        else
        {
            cout << smallCnt << " ";
            smallCnt = 1;
            ++cnt;
            sum = v[i];
        }
        if (cnt + N - i - 1 == M)
        {
            cout << smallCnt << " ";
            ++i;
            for (; i < N; ++i)
                cout << 1 << " ";
            return;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    v = vector<int>(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i];
    int start = 0, mid, end = 30001;
    while (start <= end)
    {
        mid = (start + end) >> 1;
        int cnt = 1, sum = 0;
        for (int i = 0; i < N; ++i)
            if (sum + v[i] <= mid)
                sum += v[i];
            else if (v[i] > mid)
                cnt += 30001;
            else
            {
                ++cnt;
                sum = v[i];
            }
        if (cnt <= M)
            end = mid - 1;
        else
            start = mid + 1;
    }
    print(start);
}

풀이

특정 값을 구하고 난 뒤가 문제였다.
그저 뭉쳐서 출력한다면 M보다 작아질 수 있다는 것이다.
그렇기에 뭉쳐서 출력하다가 뭉친 개수+남은 개수가 M이면 남은 개수는 1씩 출력해 주면 된다.