숫자구슬 > 문제은행

본문 바로가기


알고리즘 자료구조1

1300 : 숫자구슬

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 304 회    시도횟수: 1302 회    Special Judge



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

 

efc6e5f9d670c6da62174cf11a66a8c2_1449728 

 

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

 

efc6e5f9d670c6da62174cf11a66a8c2_1449728 

 

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


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


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

[Copy]
8 3
5 4 2 6 9 3 8 7
[Copy]
17
4 2 2





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.