[백준 2343번] 기타 레슨 (이분탐색, python, binary search)

www.acmicpc.net/problem/2343

2343번: 기타 레슨

이분탐색 자체보다는 각 크기를 잘못 계산하는 바람에 계속 틀렸다 

l=min(lesson)으로 해줬었는데 그러면 기준 크기 mid보다 각 음악의 길이가 더 클 때 문제가 된다. 

따라서 l=max(lesson)으로 해줘서 최소 한 블루레이 크기에 한 음악은 들어갈 수 있도록 해줘야한다. 

 

import sys
input=sys.stdin.readline
from collections import deque

n,m=map(int,input().split())

lesson=list(map(int,input().split()))
# print(lesson)
l=max(lesson)
r=sum(lesson)
ans=sys.maxsize
while l<=r:
    mid=(l+r)//2
    cnt=0
    sum=0
    for i in range(len(lesson)):
        if sum+lesson[i]>mid:
            cnt+=1
            sum=0
        sum+=lesson[i]
    if sum:
        cnt+=1

    if cnt>m: # 블루레이 개수가 m보다 커 (각 크기가 작음)
        l=mid+1
    else:
        ans=min(ans,mid)
        r=mid-1
print(ans)