[c++] 백준 #2613 숫자구슬 (190903)

< 풀이 > 

최댓값이 N이하가 되도록 구슬을 나눌 수 있을까? 라는 질문으로 바꾸고 Binary search를 이용하면 된다. 이는 맨 앞에서부터 구슬을 하나씩 꽉꽉 채운다고 하면 한 번 search할 때마다 O(n)에 해결 가능하다. 최댓값을 기준으로 그룹을 나누면 m <= M개의 그룹으로 나눠진다.

Binary search를 통해 최댓값이 되는 경우는 찾을 수 있는데 문제에서 추가로 요구하는 건 각 그룹의 구슬 갯수이다. 그룹을 m <= M개로 나눠버려서 이를 보정해주려면, 일단 최댓값대로 m개의 그룹으로 나누고, 모자란 갯수만큼 그룹을 쪼개서(쪼개서 1개짜리 원소를 가진 그룹을 하나 생성한다는 느낌) M개를 맞춰준다.

그룹을 쪼갤 때는 항상 최댓값이 아닌 원소를 가져온다고 생각하면 되므로 문제는 발생하지 않는다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
//#define INF 9223372036854775807
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;


#define N_MAX 301
int N, M;
int ball[N_MAX];

// 각 그룹의 합의 최댓값이 n 이하로 만드는 것이 가능한가
bool isValid(int n){
    int group_sum = 0;
    int m = 0;
    for(int i=0; i<N;i++){
        if (ball[i] > n) return false;
        if (group_sum + ball[i] <= n) group_sum += ball[i];
        else {
            m++;
            group_sum = ball[i];
        }
    }
    m++; // 맨 마지막 그룹에 대한 count
    if (m <= M) return true;
    else return false;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for(int i=0; i<N;i++){
        cin >> ball[i];
    }

    int low = 0;
    int high = (N / M) * 100; //max value

    int mid;
    int ans = INF;
    while(low <= high){
        mid = (low + high)/2;
        if (isValid(mid)){
            high = mid - 1;
            if (mid < ans) ans = mid;
        }
        else {
            low = mid + 1;
        }
    }
    cout << ans << '\n';
    
    int group_sum = 0;
    int m = 0;
    vector<int> nballs;
    nballs.pb(0);
    for(int i=0; i<N;i++){
        if (group_sum + ball[i] <= ans){
            group_sum += ball[i];
            nballs.back()++;
        } 
        else {
            m++;
            group_sum = ball[i];
            nballs.pb(1);
        }
    }
    m++;
    int diff = M - m;
    for(int i=0; i<m;i++){
        if (nballs[i] == 1) cout << "1 ";
        else {
            while(nballs[i]>=2 && diff >=1){
                cout << "1 ";
                nballs[i]--;
                diff--;
            }
            cout << nballs[i] << " ";
        }
    }
    
    return 0;
}