[백준 2613] 숫자구슬

문제

www.acmicpc.net/problem/2613

 

알고리즘

이분탐색

 

풀이

$N$개의 구슬을 $M$개로 나눌 때, 각 그룹마다의 합이 가장 큰 것이 최소가 되게 하는 문제입니다.

 

최대의 최소화. 익숙한 이분탐색의 주제입니다. $solve$함수에서 입력값을 기준으로 $M$개 이하의 그룹을 만들 수 있는지 확인합니다. 딱 $M$개가 아닌 이하도 포함을 하는 이유는 그룹을 새로이 쪼개어 $M$개의 그룹을 만들 수 있기 때문입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, M;
int v[300];

bool solve(int p) {
    int group = 1;
    int psum = 0;
    rep(i, N) {
        if (v[i] > p)
            return false;
        if (psum + v[i] > p) {
            psum = 0;
            group += 1;
            i -= 1;
        } else
            psum += v[i];
    }
    return group <= M;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    int lo = 1;
    int hi = 0;

    rep(i, N) {
        cin >> v[i];
        hi += v[i];
    }

    int best = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (solve(mid)) {
            best = mid;
            hi = mid - 1;
        } else
            lo = mid + 1;
    }

    cout << best << '\n';

    vector<int> ans;
    int psum = 0;
    int cnt = 0;
    rep(i, N) {
        if (psum + v[i] > best) {
            ans.emplace_back(cnt);
            psum = 0;
            cnt = 0;
            i -= 1;
        } else {
            psum += v[i];
            cnt += 1;
        }
    }
    ans.emplace_back(cnt);
    while (ans.size() != M) {
        for (int i = 0; i < ans.size() && ans.size() < M; ++i) {
            if (ans[i] != 1) {
                int half = ans[i] / 2;
                ans.insert(ans.begin() + i + 1, half);
                ans[i] = ans[i] - half;
            }
        }
    }
    for (auto x : ans) {
        cout << x << ' ';
    }
    return 0;
}