숫자구슬 (boj 2613)

숫자구슬 문제는 Parametric search 기법을 활용해서 풀 수 있어요. 용돈관리 문제랑 상당히 유사하고 코드도 거의 똑같습니다만..

약간의 함정이 숨어있어요.

M개의 그룹으로 나누고 각 그룹에 속한 원소의 수를 출력해줘야하는데

 

입력으로

8 5
1000 1 1 1 1 1 1 1

 

같이 극단적으로 큰 값을 주게 되면, 용돈관리 코드로는

 

1000
1 7

과 같이 그룹이 5개가 아니라 2개만 나오게 돼요

그래서 충분히 적은 수의 그룹을 만들 수 있더라도 M개에 미치지 못한다면 적절히 쪼개주는 작업이 필요하답니다.

쪼개는건 사실 쉬워요. 원소의 갯수가 2 이상인 그룹을 찾아서 1개씩 뽑아주면 됩니다. 뽑아주는 과정은 그룹의 갯수가 M이 될때까지 반복하는거구요.

 

코드

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

#define INF 987654321

int N, M;
int arr[310];
int max = 30000;
int min;
std::vector<int> result;


int parametricSearch(int k) {
    int val = k;
    int m = 1;

    for (int n = 0; n < N; n++) {
        if (val >= arr[n]) {
            val -= arr[n];
        } else {
            val = k;
            val -= arr[n];
            m++;
        }
    }

    return m <= M;
}

int main() {
    scanf("%d %d", &N, &M);

    for (int n = 0; n < N; n++) {
        scanf("%d", arr + n);

        min = std::max(min, arr[n]);
    }

    while (min != max) {
        int val = min + (max - min) / 2;
        if (parametricSearch(val)) {
            max = val;
        } else {
            min = val + 1;
        }
    }

    printf("%d\n", max);

    int value = max;
    int count = 0;
    int groupCount = 0;
    for (int n = 0; n < N; n++) {
        if (value >= arr[n]) {
            value -= arr[n];
            count++;
        } else {
            value = max;
            value -= arr[n];
            result.push_back(count);
            count = 1;
            groupCount++;
        }
    }
    result.push_back(count);

    int i = 0;
    while (result.size() < M) {
        while (result[i] <= 1)
            i++;

        result[i]--;
        result.push_back(1);
    }

    for (int r : result)
        printf("%d ", r);
    return 0;
}