[Python] 백준 2613: 숫자구슬

2613번: 숫자구슬 (acmicpc.net)

2613번: 숫자구슬

1. 이분탐색으로 구현하는 문제이다.

2. left 값을 공의 최솟값 right값을 모든공의 합으로 탐색한다.

3. 정답은 공의 최댓값보다는 커야한다.

4. (최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.) 라고 명시되어 있기 때문에 공의 그룹이 m 보다 작을경우 공을 계속해서 쪼개준다.

import math

ans = 0

n, m = map(int, input().split())
ball = list(map(int, input().split()))
lt, rt = min(ball), sum(ball)
lst = []


def groupCnt(x):
    cnt = 1
    tot = 0
    tmp = []
    ballCnt = 0
    for item in ball:
        if tot + item > x:
            cnt += 1
            tot = item
            tmp.append(ballCnt)
            ballCnt = 1
        else:
            tot += item
            ballCnt += 1
    if ballCnt:
        tmp.append(ballCnt)
    return tmp, cnt


while lt <= rt:
    mid = (lt + rt) // 2
    tmp, cnt = groupCnt(mid)
    if cnt <= m and max(ball) <= mid:
        lst = tmp
        ans = mid
        rt = mid-1
    else:
        lt = mid+1

print(ans)
while len(lst) < m:
    for i in range(len(lst)):
        if lst[i] > 1:
            tmp = lst[i]
            del lst[i]
            lst.insert(i, math.ceil(tmp/2))
            lst.insert(i, math.floor(tmp/2))
            if len(lst) == m:
                break

for x in lst:
    print(x, end=' ')