[BOJ/백준] 2613 숫자구슬

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def make_group(limit):
    temp = 0
    cnt = 0
    result = []
    group_cnt = K
    for ind in range(N):
        temp += arr[ind]
        if temp>limit:
            temp = arr[ind]
            result.append(cnt)
            group_cnt -= 1
            cnt = 0
        cnt += 1
        if group_cnt == (N-ind):
            result.append(cnt)
            group_cnt -= 1
            while group_cnt:
                result.append(1)
                group_cnt -= 1
            return result
 
def count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>val:
            temp = arr[ind]
            k += 1
    if temp:
        k += 1
    return k
 
 
N,K = map(int,input().split())
 
arr = list(map(int,input().split())) 
 
 
left = max(arr)-1
right = sum(arr)
answer = right
while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid > K:
        left = mid
    else:
        right = mid
print(right)
print(*make_group(right))

최근 풀었던 문제들 중에서 가장 어렵게 푼 문제였다.

 

이 문제는 단순한 이분탐색으로 끝나는 것이 아닌, 그룹을 구하는게 힘들었다.

 

그룹을 만드는 방식은 다음과 같다.

 

문제에 주어진 M개의 그룹을 강제적으로 만들어줘야한다.

 

즉 우리가 그룹을 만들어야하는 개수와 현재 남은 구슬의 수가 동일하다면,

 

나머지 구슬들을 전부 1개씩으로 만들어줘야한다.

 

이 점을 주의해서 풀어주면 문제를 해결할 수 있는 문제였다.