백준 온라인 저지, 이진탐색 / 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개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.

제한

예제 입력 1

8 3
5 4 2 6 9 3 8 7

예제 출력 1

17
4 2 2

힌트

접근 방법

- 현재 주어진 숫자 구슬의 모든 합을 end로, 구슬의 최댓값을 start로 하는 이진탐색을 한다.
- 구슬을 하나씩 탐색하며 숫자를 합해가다 mid보다 숫자가 커지면 숫자의 합계를 초기화하고 그룹을 하나 더 늘려간다.
- 이후 만들어진 그룹의 개수를 비교해 m과 같은 경우 mid를 .결과값으로 저장해가며 최소가 되는 길이를 찾는다.

코드

# https://www.acmicpc.net/problem/2613
# 접근 방법
# 현재 주어진 숫자 구슬의 모든 합을 end로, 구슬의 최댓값을 start로 하는 이진탐색을 한다.
# 구슬을 하나씩 탐색하며 숫자를 합해가다 mid보다 숫자가 커지면 숫자의 합계를 초기화하고 그룹을 하나 더 늘려간다.
# 이후 만들어진 그룹의 개수를 비교해 m과 같은 경우 mid를 .결과값으로 저장해가며 최소가 되는 길이를 찾는다.
n, m = map(int, input().split())
marble = list(map(int, input().split()))
start = max(marble)
end = sum(marble)
min_max_value = sum(marble)
while start <= end:
    mid = (start+end) // 2
    total = 0
    count_marble = 0
    count_ = []
    for i in range(n):
        if marble[i] + total > mid:
            total = 0
            count_.append(count_marble)
            count_marble = 0
            
        elif n - i < m - len(count_):
            total = 0
            count_.append(count_marble)
            count_marble = 0
            
        total += marble[i]
        count_marble += 1
        
    if count_marble:
        count_.append(count_marble)
        
    count_group = len(count_)
    if count_group == m:
        if min_max_value >= mid:
            min_max_value = mid
            result = count_
        end = mid - 1
        
    elif count_group > m:
        start = mid + 1
        
    else:
        end = mid - 1

print(min_max_value)
for x in result:
    print(x, end=' ')