[백준] 2613 숫자 구슬

문제

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

이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, <그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.

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

입력

첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다.

출력

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.

 

 

숫자구슬들을 하나의 수열로 바꾸면 문제는 다음과 같이 쓸 수 있습니다.

한 수열을 M개의 부분수열로 나누었을 때, 각 부분수열 합의 최댓값이 최소값을 구하고, 각 부분수열 요소의 수를 순서대로 출력하라.

 

부분수열의 합의 최댓값을 K라 할때 , K로 나눌 수 있는 최소 그룹의 수가 M일때 답을 구할 수 있습니다.

이분탐색을 사용합니다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, M, arr[5000];
vector<int>answer;
ll check(ll mid) {
	int temp = 0, cnt = 0, num = 0;
	for (int i = 0; i < N; i++) {
		if (arr[i] > mid)return M + 1;

		if (temp + arr[i] <= mid) {
			num++;
			temp += arr[i];
		}
		else {
			cnt++;
		
			num = 1;
			temp = arr[i];
		}
	}

	return ++cnt;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	ll le = 0, ri = 300001, mid, ans;
	while (le <= ri) {
		mid = (le + ri) / 2;
		if (check(mid) <= M) { //부분수열의 합이 mid보다 작을때 부분수열의 개수가 M개보다 작거나 같으면
			ri = mid - 1;
			ans = mid;
		}
		else le = mid + 1; 
	}
	cout << ans << "\n";
	int cnt = N - M + 1, temp = 0, num = 0; //cnt번 merge해야함
	for (int i = 0; i < N; i++) {
		if (cnt == 0) {
			cout << 1 << " ";
			continue;
		}
		if (temp + arr[i] <= ans) {
			temp += arr[i];
			num++;
			cnt--;
			if (cnt == 0) {
				cout << num << " ";
			}
		}
		else {
			cout << num << " ";
			temp = arr[i];
			num = 1;
		}
	}
	if(cnt)cout << num;

}

K를 찾았으면 마지막에 출력을 할땐, N개를 N-M번 merge 하고, merge를 마친 후에는 각 하나씩만 배열하면 됩니다.