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

---

접근

이진탐색을 통해 상한선을 구한다. 이후 상한선을 통해 그룹을 나누고 그룹이 나눠진 개수를 통해 이진탐색의 범위를 결정하도록 한다.

 

left의 범위는 숫자 중에 최댓값으로 한다. 왜냐하면 한 개의 그룹에 최소 한 개의 숫자구슬이 포함되어야 하는데 최댓값보다 작은 수로 하면 그룹에 포함되지 않는 구슬이 있을 수 있다. 이어서 right는 모든 숫자의 합으로 정한다.

 

이제 left와 right를 통해 mid값을 구하고 mid로 그룹을 나눌 때 몇 개의 그룹이 나눠지는지 계산하고 M 이하일 때는 right를 줄이고, 반대일 때는 left를 올린다.

 

구현

- left < right로 할 경우 마지막에 15, 16이 되었을 때 답을 찾지 못할 수 있다. 따라서 left <= right로 하여 두 개의 값이 같을 때도 다음 비교를 하도록 한다.

- 이제 mid로 M개를 초과하여 그룹을 만들 때 (else 구문) 최댓값을 찾도록 한다. 초과해서 만든다는 것은 한 개의 그룹을 정할 때 상한선을 작게 잡았다는 것이다.

- 따라서 left의 범위를 올려주고 최댓값 비교를 하여 answer를 갱신한다.

while left <= right:
    mid = (left + right) // 2
    if is_possible(mid):
        right = mid - 1
    else:
        left = mid + 1
        answer = max(answer, left)

- 최댓값을 모두 구한 다음에 각 그룹에 몇 개의 숫자구슬이 포함되어있는지 구한다.

- 숫자구슬을 처음부터 탐색하여 더하고 최댓값보다 클 때는 m을 감소하고 count를 최종해에 담는다.

- 만약 N-idx가 m이 되었다면 종료하여 한 개의 그룹에 최소 한 개의 숫자구슬을 포함하도록 한다.

def solve(target):
    count = 0
    total = 0
    result = []
    m = M
    for idx in range(N):
        total += numbers[idx]
        if total > target:
            m -= 1
            total = numbers[idx]
            result.append(count)
            count = 0
        count += 1
        if N - idx == m:
            break

    while m:
        result.append(count)
        count = 1
        m -= 1
    return result

---

전체 코드

import sys
input = sys.stdin.readline

def is_possible(target):
    grpCnt = 1
    total = 0
    for number in numbers:
        total += number
        if total > target:
            grpCnt += 1
            total = number

    return grpCnt <= M

def solve(target):
    count = 0
    total = 0
    result = []
    m = M
    for idx in range(N):
        total += numbers[idx]
        if total > target:
            m -= 1
            total = numbers[idx]
            result.append(count)
            count = 0
        count += 1
        if N - idx == m:
            break

    while m:
        result.append(count)
        count = 1
        m -= 1
    return result


N, M = map(int, input().split())
numbers = list(map(int, input().split()))
left = max(numbers)
right = sum(numbers)

while left <= right:
    mid = (left + right) // 2
    if is_possible(mid):
        right = mid - 1
    else:
        left = mid + 1

print(left)
print(*solve(left))