숫자 구슬

면접 대비

시간 제한1초메모리 제한128 MB

요약

순서가 있는 배열을 M개의 연속 구간으로 나눠 구간 합의 최댓값을 최소화하고, 그 값과 각 구간의 길이를 출력합니다.

문제

N개의 숫자 구슬이 막대에 꿰어진 순서대로 일렬로 놓여 있다. 구슬은 막대에서 빼낼 수 없고, 순서를 바꿀 수도 없다.

이 구슬들을 순서를 유지한 채 M개의 연속한 그룹으로 나누려고 한다. 각 그룹에는 구슬이 적어도 하나 있어야 한다. 어떤 나누기에서 각 그룹의 숫자 합을 구했을 때, 그중 최댓값이 가능한 한 작아지도록 해야 한다.

조건을 만족하도록 M개의 그룹으로 나눌 때 가능한 최소 최댓값과, 왼쪽부터 각 그룹에 들어가는 구슬의 개수를 출력하는 프로그램을 작성하시오.

첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에 각 구슬에 적힌 숫자가 왼쪽부터 순서대로 주어진다.

첫째 줄에 각 그룹 합의 최댓값을 최소로 만들었을 때의 값을 출력한다. 둘째 줄에 왼쪽부터 각 그룹을 이루는 구슬의 개수를 공백으로 구분해 출력한다.

최적의 나누기가 여러 가지라면 그중 아무 것이나 출력해도 된다.