숫자구슬 (백준 2613)

안녕하세요. 오늘은 숫자 구슬을 나눌 거예요.

문제

https://www.acmicpc.net/problem/2613

아이디어

최댓값의 최솟값은 파라메트릭 서치로 비교적 쉽게 구할 수 있습니다. 특정한 값이 정답으로 가능한지만 보면 되지요. cal(x)를 x를 정답으로 가정했을 때 가능한 최소 그룹의 개수이므로 cal(x)<=M이면 x는 가능으로 판별할 수 있습니다.
하지만 진짜 문제는 출력입니다. 개수가 정확히 M개가 되어야하기 때문에 조금 특별하게 출력할 겁니다. 벡터에 일단 다 때려넣고 tot에 총 출력 개수를 저장합니다. 초깃값은 벡터의 size입니다. 이때 분할을 할 건데 v[i]가 1보다 크다면 1과 v[i]-1로 쪼갤 수 있습니다. 그러므로 tot++을 하고 1을 출력하고 v[i]--를 해주면 간단하게 해결이 가능합니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll N, arr[333] = { 0 };
ll cal(ll x)
{
    ll cnt = 1, sum = 0;
    for (ll i = 1; i <= N; i++)
    {
        if (sum + arr[i] > x)
        {
            cnt++;
            sum = 0;
        }
        sum += arr[i];
    }
    return cnt;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, i, mx = 0;

    cin >> N >> M;
    for (i = 1; i <= N; i++)
    {
        cin >> arr[i];
        mx = max(mx, arr[i]);
    }

    ll left = mx, right = 30000, mid, ans;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (cal(mid) <= M) //가능
        {
            ans = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }

    cout << ans << "\n";

    vector <ll> v;
    ll cnt = 0, sum = 0;
    for (ll i = 1; i <= N; i++)
    {
        if (sum + arr[i] > ans)
        {
            v.push_back(cnt);
            cnt = 0;
            sum = 0;
        }
        sum += arr[i];
        cnt++;
    }
    v.push_back(cnt);

    ll tot = v.size();
    for (ll i = 0; i < v.size(); i++)
    {
        if (tot < M) //부족하면
        {
            if (v[i] > 1) //1보다 크면
            {
                //분할
                cout << "1 ";
                v[i]--;
                i--;
                tot++;
            }
            else //1이면
            {
                cout << v[i] << ' ';
            }
        }
        else //아니면
        {
            cout << v[i] << ' ';
        }
    }
}

감사합니다.