[BOJ 2613] 숫자구슬

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

2613번: 숫자구슬

 

- 문제 요약

 

N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다.

이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 한다.

그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최댓값과 각 그룹을 구성하는 구슬의 개수를 찾아 출력하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

이분탐색으로 해결할 수 있는 문제입니다.

left, right 변수를 설정할 때 입력받은 구슬의 값 중 최댓값을 left로 설정하고 이분탐색을 진행합니다.

그룹을 만들 수 있는 상황인지, 아닌지를 판단하면서 그리디하게 문제를 해결해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 301
int n,m,arr[MAX],l,r,result,mid;

bool check(int x){
	int sum=0,cnt=1;
    for(int i=0;i<n;i++){
        sum+=arr[i];
        if(sum>x){
            sum=arr[i];
            cnt++;
        }
    }
    return cnt<=m;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		l=l<arr[i]?arr[i]:l;
        r+=arr[i];
	}
	while(l<=r){
		mid=(l+r)/2;
        if(check(mid))
            r=mid-1;
        else
            l=mid+1;
	}
	cout<<l<<'\n';
    int sum=0,w=0;
    for(int i=0;i<n;i++){
    	sum+=arr[i];
    	if(sum>l){
    		sum=arr[i];
    		m--;
    		cout<<w<<" ";
    		w=0;
		}
		w++;
		if(n-i==m){
			break;
		}
	}
	while(m--){
		cout<<w<<" ";
		w=1;
	}
}

코드 제출 결과