https://www.acmicpc.net/problem/2613
2613번: 숫자구슬
첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100
www.acmicpc.net
- 왼쪽부터 차례대로 숫자구슬을 묶으면서 묶여있는 구슬의 합의 최댓값이 최소가 되게 하는 문제.
- 처음엔 간단하게 조합을 이용하여 풀어보려고 했지만, 골드2 문제답게 조합으로 풀면 시간 초과가 나게 된다.
- 이분탐색과 그리디 알고리즘을 이용하여 시간을 낮추어 풀 수 있었다.
- 숫자구슬 묶음의 개수는 최소 1개 최대 N개가 된다
- 숫자구슬 묶음을 1개로 두었을 때 최대값은 리스트의 전체 합 즉, sum(n_lst)가 될 것이고, 숫자구슬 묶음을 N개로 두었을 경우 최대값은 리스트 요소 중 최대값 max(n_lst)가 될 것이다
- 결국 숫자구슬 묶음의 최댓값은 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)