N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다.
이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, <그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.
각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최댓값과 각 그룹을 구성하는 구슬의 개수를 찾아 출력하는 프로그램을 작성하시오.
첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다.
출력
각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.
입력 예시
8 3
5 4 2 6 9 3 8 7
출력 예시
17
4 2 2
풀이
이 문제는 여러 가지 풀이법을 적용해 볼 수 있을 것 같다. 지금 소개할 접근법은 DP를 이용한 풀이이며, 다른 풀이(예를 들면 매개변수 이분 탐색) 역시 충분히 가능해 보인다.
dp[j][i]를 j번째 이전 구슬을 가지고 총 i개의 묶음으로 만들었을 때의 최댓값의 최솟값이라고 정의하자. 임의의 dp[k][i-1] (k<j)에 대하여, k부터 j까지의 구슬 묶음의 합을 구할 수 있다. 여기서 유도되는 최댓값 maxval은 max(dp[k][i-1], sum[k] - sum[j])가 되며, dp[j][i] = min(maxval, dp[j][i])로 업데이트 가능하다.
또한 본 문제에서는 각 그룹을 구성하는 구슬 개수 역시 출력해야 하므로, 업데이트되는 경우마다 이전 노드를 저장하는 방식 등으로 백트래킹 가능하게 바꾸어줄 필요가 있겠다.
풀이 코드
MAX = float('inf')
N, M = map(int, input().split())
marble_list = list(map(int, input().split()))
sum_marble_list, sum_val = [0], 0
for m in marble_list :
sum_val += m
sum_marble_list.append(sum_val)
dp = [[(MAX, -1)]*(M+1) for _ in range(N+1)]
dp[0][0] = (0, 0)
for i in range(1, M+1) :
for j in range(1, N+1) :
for k in range(j) :
if dp[k][i-1][0] == MAX :
continue
maxval = max(dp[k][i-1][0], sum_marble_list[j] - sum_marble_list[k])
if maxval < dp[j][i][0] :
dp[j][i] = (maxval, k)
answer, prev, idx = [0]*M, N, M
while idx :
_, _prev = dp[prev][idx]
answer[idx-1] = prev - _prev
prev = _prev
idx -= 1
print(dp[-1][-1][0])
print(*answer)
