백준 문제풀이 - 2613 번
1. 요약 및 풀이방법
막대에 꿰어져 있는 N개의 숫자 구슬을 M개의 그룹으로 나누었을 때, 각 그룹의 합 중 최댓값이 최소가 되도록 하는 문제입니다.
생각보다 어렵고 예외도 많이 발생한 문제였습니다.
우선 문제에서 요구하는 "그룹의 합 중 최댓값이 최소가 되도록 한다" 는 말의 의미는 M개의 그룹의 합이 최대한 비슷하게 그룹을 나누라는 의미입니다.
각 그룹의 합의 가능한 범위를 정하고, 이 범위의 mid 값을 구하여 이분탐색으로 문제를 해결했습니다.
즉 여기서 구해진 mid 값은, 특정 반복문에서 각 그룹이 가질 수 있는 최대값입니다.
각 그룹의 합은 이 mid값보다 작도록 나누어지고,
이렇게 그룹을 나눈 결과 M개의 그룹보다 적거나 같게 나눠지면 mid값을 낮춰 각 그룹의 상한을 낮춥니다.
이렇게 하면 한 그룹에 들어갈 수 있는 구슬들이 나눠지면서 그룹의 수가 늘어나게 됩니다.
또는 M개의 그룹으로 나눠진 경우 그룹 중 최댓값을 낮출 수 있습니다.
또한 M개의 그룹 보다 많이 나뉘면, 현재 너무 잘게잘게 그룹을 나누고 있다는 뜻이므로, mid값을 키워줍니다.
그리고 구슬을 그룹으로 나누는 도중에 남은 그룹의 갯수와 남은 구슬의 갯수가 같은 경우,
(즉, 총 4그룹으로 나눠야 하는데 현재까지 2그룹 만들었고, 이때 남은 구슬이 2개인 경우)
각 그룹에는 mid 값과 상관없이 구슬을 한개씩만 넣어야 합니다.
자세한 내용은 코드에 주석으로 달아두었습니다.
2. Code
def main():
N, M = map(int, input().split())
nums = list(map(int, input().split()))
ans = 0 # 최종 그룹합의 최대값
group = [] # 각 그룹을 구성하는 구슬의 갯수
start = max(nums) # 그룹합의 하한
end = sum(nums) # 그룹합의 상한
while start <= end:
mid = (start + end) // 2 # 현재 그룹합의 최대값 기준
group_cnt = 0 # 이번에 만들어진 그룹의 갯수
idx = 0
group = []
while idx < N:
sub_sum = 0 # 특정 그룹의 합
sub_count = 0 # 특정 그룹을 구성하는 구슬의 갯수
while idx < N and sub_sum + nums[idx] <= mid: # 각 그룹의 합이 mid보다 작도록 구슬 넣기
sub_sum += nums[idx]
sub_count += 1
idx += 1
if M - group_cnt == N - (idx - 1): # 남은 그룹의 갯수와 남은 구슬의 갯수가 같은 경우, 한 그룹에 하나의 구슬만 넣기 위해 break
break
group_cnt += 1 # 만들어진 그룹 수 증가
group.append(sub_count) # 각 그룹의 구슬 갯수 리스트에 추가
if group_cnt <= M: # 그룹이 M개보다 적거나 같은 경우, mid를 작게 만들어 더 잘게 쪼갤 수 있도록, 또는 최대값이 최소가 되도록 함
end -= 1
else: # 그룹이 M개보다 큰 경우, mid를 키워 더 많은 구슬을 한 그룹에 담을 수 있도록 함
start += 1
ans = mid
print(ans)
print(*group)
if __name__ == "__main__":
main()
3. 학습 내용
우선 다시한번 이분탐색의 start, end 값 초기화의 중요성에 대해 배웠습니다.
이 문제에서는 start 값을 구슬들 중 max 값으로 시작해야 합니다.
1이나 min 값으로 start를 초기화 하게 되면, 그룹에 들어가지 못하는 구슬이 발생하기 때문입니다.
또한 결과를 출력할 때, 리스트의 원소를 한칸의 공백으로 구분하여 출력하는 부분에서,
사실 처음에 생각보다 당황했습니다.
출력만을 위해 또 코드를 짜야하나 싶었지만 python에서는 *를 사용하여,
리스트나 튜플 등 컨테이너 타입의 데이터를 쉽게 unpaking 할 수 있었습니다.
4. 결과
