[백준]숫자구슬(2613)

문제 링크 : [백준]숫자구슬(2613)

문제 설명

N개의 숫자가 적힌 구슬이 있고, 그 구슬을 연속된 구간 M개로 나눌 때, 각 구간의 합의 최댓값이 최소가 되는 값을 구하고, 각 구간마다 몇개의 구슬이 있는지를 구하세요.

입력

N(구슬의 수, 1 <= N <= 300)
M(그룹의 수, 1 <= M <= N)
V_i(각 구슬에 적힌 수, 1 <= A_i <= 100)

8 3
5 4 2 6 9 3 8 7

출력

17
4 2 2

카테고리

#이분탐색

시간 복잡도 상한

O(N³)

해결 방법

1. 모든 경우의 수를 구하려면 대략 _nC_m 정도의 시간이 걸려 타임아웃이 될 것입니다.
2. 각 구간의 최댓값을 정해놓고, 그 최댓값 안에서 구간을 나눌 수 있는지를 판별하는 것은 각 값에서 N번만에 구할 수 있습니다.
3. 즉 30000 * N안에 구할 수 있습니다.
4. 시간이 조금 아슬아슬하니 이분탐색을 고려해봅니다.
5. 정해진 최댓값으로 M개 이하의 그룹으로 나눌 수 있다면, 그때 나눈 곳들을 저장하고, 최댓값을 줄여봅니다.
6. 반대로 정해진 최댓값으로 M개 이상으로 그룹을 나누어야 한다면 최댓값을 늘립니다.
7. 이렇게 구한 최댓값의 최솟값을 출력해줍니다.
8. 그리고 나눈 그룹이 M보다 작다면, 그룹안에 구슬의 갯수가 2 이상인 곳을 부족한 그룹만큼 나누어 출력하면 됩니다.

시간복잡도

O(N * log30000)

코드

#include<cstdio>
#include<vector>
using namespace std;
int n,m,d[300],l,r=30001,i,s,c,a,x;
vector<int>v,w;
int main(){
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)scanf("%d",d+i);
    while(l<=r){
        s=c=(l+r)/2;
        v.clear();
        v.push_back(0);
        for(x=1,i=0;i<n;i++){
            if(c<d[i]){x=m+1;break;}
            if(s<d[i])x++,s=c,v.push_back(i);
            s-=d[i];
        }
        if(x<=m){
            a=c;w.clear();
            v.push_back(n);
            for(i=1;i<v.size();i++)w.push_back(v[i]-v[i-1]);
            r=c-1;
        }
        if(x>m)l=c+1;
    }
    printf("%d\n",a);
    for(i=0;i<w.size();i++){
        if(w.size()<m&&w[i]>1)printf("%d ",1),m--,w[i--]--;
        else printf("%d ",w[i]);
    }
}