[python] 코딩테스트 대비 - 이분검색(최소 길이 구하기)

문제)

답안 코드)

import sys
#sys.stdin=open("input.txt", "r")
def Count(capacity):#해당 용량으로 만들 수 있는 dvd 갯수 리턴
    cnt=1
    sum=0
    for x in Music:
        if sum+x>capacity:
            cnt+=1
            sum=x
        else:
            sum+=x
    return cnt
 
n, m=map(int, input().split())
Music=list(map(int, input().split()))
 
maxx=max(Music)#음악 중 최고 용량
lt=1
rt=sum(Music)#1개 dvd에 모든 노래를 넣을 경우까지 범위 지정
res=0
 
while lt<=rt:
    mid=(lt+rt)//2
    if mid>=maxx and Count(mid)<=m:#만들 수 있는 dvd 수가 m보다 작다면,(1개의 dvd 용량이 너무 큰것, 정답가능)
        res=mid#정답에 넣고
        rt=mid-1#더 적은 용량으로 만들 수 있는지 탐색
    else:#작다면
        lt=mid+1
print(res)