들쮜의 개발자일지

https://www.acmicpc.net/problem/2613

• 왼쪽부터 차례대로 숫자구슬을 묶으면서 묶여있는 구슬의 합의 최댓값이 최소가 되게 하는 문제.
• 처음엔 간단하게 조합을 이용하여 풀어보려고 했지만, 골드2 문제답게 조합으로 풀면 시간 초과가 나게 된다.
• 이분탐색과 그리디 알고리즘을 이용하여 시간을 낮추어 풀 수 있었다.

1. 숫자구슬 묶음의 개수는 최소 1개 최대 N개가 된다
2. 숫자구슬 묶음을 1개로 두었을 때 최대값은 리스트의 전체 합 즉, sum(n_lst)가 될 것이고, 숫자구슬 묶음을 N개로 두었을 경우 최대값은 리스트 요소 중 최대값 max(n_lst)가 될 것이다
3. 결국 숫자구슬 묶음의 최댓값은 max(n_lst) <= X sum(n_lst)가 될 것이기 때문에 해당 값이 이분탐색으로 구한뒤 최댓값으로 가능한지 그리디 알고리즘을 이용하면 풀면 되는 문제였다.

** 이분탐색을 사용하기 위해 start, end값 설정해주기 **

N, M = map(int, input().split())

n_lst = list(map(int, input().split()))

# 이분탐색을 하기 위해 start와 end값을 찾아야 함
# start값은 1개를 담았을 경우의 최댓값
# end값은 한번에 모든 것을 담았을 경우의 최댓값
# M개의 묶음을 만들어 값을 만들어낼 수 있는 경우를 찾았더라도 최댓값 중 최솟값을 찾아야 하므로 더 낮춰야 함 (end값 낮추기)
start = max(n_lst)
end = sum(n_lst)
min_ans = int(1e9)

** 이분탐색을 돌리면서 최댓값이 가능한지 체크해주고, 그리디 알고리즘을 이용하여 M개의 묶음이 가능한지를 체크 **

• 1, 2, 3, 4, 5 이 구슬들 중 현재 최댓값이 가능한지 체크하는 숫자를10이라고 정해두었다고 생각해보자
• (1, 2, 3, 4) (5) 이렇게 묶음을 나눌 수 있는데, 이 때 만약 내가 구슬을 3개의 묶음으로 만들고자했다면 4개의 구슬을 분할해주면 된다. 그렇기 때문에 내가 묶고 싶은 묶음의 개수 M개보다 작은 경우에도 M개의 묶음이 가능하게 된다.

while start <= end:
    mid = (start + end) // 2
    cnt = 0 #묶음의 개수
    sum = 0 #현재 묶음의 값
    sum_lst = []
    cnt_lst = []
    for i in range(len(n_lst)):
        check = sum + n_lst[i] #현재 묶음에 구슬을 추가로 넣을 수 있는지 체크
        if check > mid: #만약 현재 묶음에 구슬을 추가로 넣을 수 없다면
            cnt_lst.append(cnt) #현재 구슬의 개수와 값을 넣어두고
            sum_lst.append(sum)
            sum = 0 #묶음 구슬의 개수와 값을 초기화시켜준다
            cnt = 0
        # 그런 뒤 다시 값과 개수를 늘려주면 그리디 알고리즘 완료        
        sum += n_lst[i]
        cnt += 1
    #반복문의 마지막은 값과 개수를 늘려주는 것으로 끝나므로 마지막에 추가해준 값과 개수까지 append로 따로 넣어준다.
    sum_lst.append(sum)
    cnt_lst.append(cnt)

** 그리디 알고리즘이 끝났으면 해당 묶음의 개수를 체크하고, 원하는 M개보다 작거나 같으면 개수와 값을 갱신해준다. **

    if len(sum_lst) <= M: # 만들어진 개수가 M보다 작거나 같다면 해당 값으로 묶음을 만들 수 있다

        end = mid - 1 # 좀 더 작은 최댓값으로도 묶음을 만들 수 있는지 체크하기 위해 end = mid - 1

        if max(sum_lst) < min_ans:
            min_ans = max(sum_lst) 
            min_cnt = cnt_lst
    else:
        start = mid + 1
print(min_ans)

** 이제 추가로 작업을 해주어야 할 것은 묶음이 M개보다 작을 경우의 체크이다 **

while len(min_cnt) != M: #묶음의 개수가 같아질 때 까지
   if min_cnt[i] == 1 : # 묶음 안의 구슬 개수가 1개일 경우 
       i += 1 #다음 구슬 체크
   else : #묶음 안의 구슬 개수가 1개를 초과할 경우
       min_cnt[i] -= 1 #해당 묶음의 구슬 개수를 하나 줄이고
       min_cnt.insert(i+1, 1) #그 묶음의 바로 앞에 추가로 구슬 묶음을 만들어준다.
print(*min_cnt)

** 최종코드 **

N, M = map(int, input().split())

n_lst = list(map(int, input().split()))

# 이분탐색을 하기 위해 start와 end값을 찾아야 함
# start값은 1개를 담았을 경우의 최댓값
# end값은 한번에 모든 것을 담았을 경우의 최댓값
# M개의 묶음을 만들어 값을 만들어낼 수 있는 경우를 찾았더라도 최댓값 중 최솟값을 찾아야 하므로 더 낮춰야 함 (end값 낮추기)
start = max(n_lst)
end = sum(n_lst)
min_ans = int(1e9)

while start <= end:
    mid = (start + end) // 2
    cnt = 0 #묶음의 개수
    sum = 0 #현재 묶음의 값
    sum_lst = []
    cnt_lst = []
    for i in range(len(n_lst)):
        check = sum + n_lst[i] #현재 묶음에 구슬을 추가로 넣을 수 있는지 체크
        if check > mid: #만약 현재 묶음에 구슬을 추가로 넣을 수 없다면
            cnt_lst.append(cnt) #현재 구슬의 개수와 값을 넣어두고
            sum_lst.append(sum)
            sum = 0 #묶음 구슬의 개수와 값을 초기화시켜준다
            cnt = 0
        # 그런 뒤 다시 값과 개수를 늘려주면 그리디 알고리즘 완료
        sum += n_lst[i]
        cnt += 1
    #반복문의 마지막은 값과 개수를 늘려주는 것으로 끝나므로 마지막에 추가해준 값과 개수까지 append로 따로 넣어준다.
    sum_lst.append(sum)
    cnt_lst.append(cnt)

    if len(sum_lst) <= M: # 만들어진 개수가 M보다 작거나 같다면 해당 값으로 묶음을 만들 수 있다

        end = mid - 1 # 좀 더 작은 최댓값으로도 묶음을 만들 수 있는지 체크하기 위해 end = mid - 1

        if max(sum_lst) < min_ans:
            min_ans = max(sum_lst)
            min_cnt = cnt_lst
    else:
        start = mid + 1
print(min_ans)
i = 0

while len(min_cnt) != M: #묶음의 개수가 같아질 때 까지
   if min_cnt[i] == 1 : # 묶음 안의 구슬 개수가 1개일 경우
       i += 1 #다음 구슬 체크
   else : #묶음 안의 구슬 개수가 1개를 초과할 경우
       min_cnt[i] -= 1 #해당 묶음의 구슬 개수를 하나 줄이고
       min_cnt.insert(i+1, 1) #그 묶음의 바로 앞에 추가로 구슬 묶음을 만들어준다.
print(*min_cnt)