숫자구슬 - 2613

//2613 - 숫자구슬
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
int arr[301];
int sub[301];
 
int main()
{
    int left = 0;
    cin >> N >> M;
    for(int i = 1; i<=N; ++i)
        cin >> arr[i], left = max(left, arr[i]);
    sub[0] = 0;
    for(int i = 1; i<=N; ++i)
        sub[i] = sub[i-1] + arr[i];
    int right = sub[N];
    int ans;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int cnt = 1;
 
        int bef = 0;
        for(int i = 1; i<=N; ++i)
            if(sub[i] - sub[bef] > mid)
            {
                ++cnt;
                bef = i-1;
            }
 
        if(cnt <= M)
        {
            right = mid - 1;
            ans = mid;
        }
        else
            left = mid + 1;
    }
 
    cout << ans << "\n";
    vector<int> num;
    vector<int> size;
    int bef = 0;
    for(int i = 1; i<=N; ++i)
        if(sub[i] - sub[bef] > ans)
        {
            num.push_back(i-bef-1);
            size.push_back(sub[i-1] - sub[bef]);                               
            bef = i-1;
        }
    num.push_back(N-bef);
    size.push_back(sub[N] - sub[bef]);
    int nsize = num.size();
    for(int i = 0; i<num.size(); ++i)
    {
        while(nsize < M && num[i] > 1)
        {
            cout << "1 ";
            ++nsize;
            --num[i];
        }
        cout << num[i] << " ";
    }
}

 

 

 

 

 

 

 

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

2613번: 숫자구슬

 

 

 

 

 

 

 

숫자구슬

구슬을 m개의 집합으로 나누었을때, 그떄 구슬에 적혀있는 숫자의 합의 최대값이 최소가 되도록 나누는 문제입니다.

이때의 최대값이 얼마인지 구하기 위해서 이분탐색을 사용했습니다.

가질수 있는 최대값의 범위는 [구슬에 적힌 가장 작은 수 .... 전체 구슬에 적힌 모든 수의 합]

입니다.

 

이분탐색

1, 최대값 후보를 넘지 않는 범위내에서 구슬의 구간을 나누었을때 구간이 m보다 같거나 작으면, 정답의 후보가 됩니다. 하지만 더 최적의 해가 있을수 있으니 가능한 최대값을 더 낮추어 탐색합니다.

2. 최대값 후보를 넘지 않는 범위내에서 구슬의 구간을 나누었을때 구간이 m보다 크다면, 해당 최대값으론 절대 구간 m을 만들수 없기에 가능한 최대값을 더 높여 다시 시도합니다.

 

위의 방법으로 구해진 최대값은 m개의 집합을 만드는 최대값중 최소입니다.

각 집합에 포함된 구슬의 개수를 구하기 위해선

구해진 최대값을 넘지않게 구슬들을 나눠주고, 집합의 개수가 m가 같아지게 분할하는 작업을 해주면 됩니다.

 

왜 위와 같은 작업을 해주냐면, 

9 8

1 1 1 1 1 1 1 1 1

와 같은 경우

최대값은 2가 나오지만

최대값을 넘지않게 구슬을 나눠주면

2 2 2 2 1

로 집합이 5개뿐만 나오기 때문에

8개로 맞춰주기 위해 몇몇 집합들을 쪼개주어야 합니다.

 

저는 쪼개주는 과정에서 최대값 구간이 나누어져 전체 최대값이 변경될 수도 있지 않을까

라는 걱정을 했었는데,

만약 위처럼 최대값이 변경되게 된다면, 애초에 이분탐색에서 위와 같은 최대값이 나오지 않고 더적은 최대값이 나왔을 것입니다.

따라서 전체 최대값이 쪼개는 과정에서 변경되는 경우는 이분탐색에서 나온 최대값이 최소의 최대값이라는 것과 서로 모순임으로 아무걱정없이 집합들을 쪼개어 m개의 구간으로 나누어 주면 됩니다.