[백준/python] 16401 과자 나눠주기

16401번: 과자 나눠주기 (acmicpc.net)

16401번: 과자 나눠주기

문제 코드

m,n=map(int,input().split())
l=sorted(list(map(int,input().split())))
if m> sum(l):
    x=0
else:
    left=1
    right=l[-1]
    while left<=right:
        mid=(left+right)//2
        cnt=0
        for i in range(n):
            cnt+=l[i]//mid
        if cnt>=m:
            x=mid
            left=mid+1
        else:
            right=mid-1

print(x)

코드 해석

가장 작은 자연수인 1의 길이도 안되면 0으로 출력. 그게 아니라면 줄 수 있는 가장 긴 길이를 찾기 위해 이진탐색. 가장 작은 길이인 1, 가장 큰 길이를 left와 right로 두고 mid를 가장 긴 길이라고 설정하여 검증. 모든 l을 mid의 길이로 나눴을때 그 수가 아이들의 수m보다 크면 정답일 수 있으니 x에 저장. 이보다 큰 수를 검증해보기위해 left를 mid보다 1큰수로 저장하고 다시 탐색. 만약 mid로 나눴을때 m보다 작으면 길이를 더 줄여야하므로 right를 mid-1로 주고 다시 탐색.