[백준] 2613 - 숫자구슬

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

2613번: 숫자구슬

 

주어진 수열을 M개의 그룹으로 나누어 그룹의 합이 최소가 되도록 만드는 문제였다.

 

핵심은 파라메트릭 서치를 이용하는 것이었다.

 

1. 이분 탐색을 이용해 그룹의 최댓값을 구한다.
   • 이때 탐색 초기 최솟값은 수열의 최댓값이고, 최댓값은 수열의 합이라는 점을 주의해야 한다.
2. 그룹의 최댓값을 구하였으면 수열을 전체 탐색하며 그룹을 나눈다.
   • 스페셜 저지가 달려있는 문제인 만큼, 답만 맞다면 어떻게 나누어도 상관이 없다.
   • 따라서 왼쪽부터 최대한 많은 수가 들어가게 그룹에 집어넣는다.

 

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int a[300];
int main() {
	cin >> n >> m;
	int left = 0, right = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (left < a[i])left = a[i];
		right += a[i];
	}
	
	while (left <= right) {
		int mid = (left + right) / 2;
		int g = 1, sum = 0;
		for (int i = 0; i < n; i++) {
			if (sum + a[i] > mid) {
				g++;
				sum = a[i];
			}
			else {
				sum += a[i];
			}
		}
		if (g > m) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << left << '\n';
	int cnt = 0, sum = 0;
	for (int i = 0; i < n; i++) {
		if (sum + a[i] > left) {
			sum = a[i];
			m--;
			cout << cnt << ' ';
			cnt = 1;
		}
		else {
			cnt++;
			sum += a[i];
		}
		if (n - i == m)break;
	}
	while (m--) {
		cout << cnt << ' ';
		cnt = 1;
	}
}