전체 코드 및 해설

import sys
import math

# @param mid >= max(lectures)
def get_blueray_count(lectures:list[int],mid:int)->int:
    count=0
    sums=0

    for i in range(len(lectures)):
        if sums+lectures[i]>mid:
            sums=0
            count+=1

        sums+=lectures[i]

    return count+1


def main():
    n,m=list(map(int,sys.stdin.readline().split(' ')))
    lectures=list(map(int,sys.stdin.readline().split(' ')))

    """
    1. 문제 특성 이해하기

    m개의 블루레이는 모두 크기가 같아야 한다.
    크기가 모두 같아야 하는 블루레이의 크기를 x라 하자. 각 블루레이에 담기는 강의 시간의 합은 x 이하이다.

    이 x를 얻어내려면 어떻게 해야할까? 각 구간 마다의 시간의 합을 계산해야 한다.
    각 구간 마다의 시간의 합을 계산하는 건, O(n)이다. 이보다 더 빨리할 수는 없다. 
    왜냐하면 전체 강의를 순회하는 것은 반드시 해야하는 것이기 때문이다. (안 그러면 어떻게 각 구간의 시간의 합을 계산해?)

    따라서 이 문제는 반드시 각 구간 마다의 시간의 합을 계산하는 로직이 필요하다.
    """

    """
    2. 무식하게 풀기
    이제 x의 최소를 찾아야 한다. 규칙성이 있는지 확인하기 위해 무식하게 풀어보자.
    그전에 x의 범위를 먼저 확인하자.
    예를 들어, 예제 입력 2 2 3 4 5가 있을 때, x의 범위는 5부터 16이다.
    블루레이 개수 m은 1 이상이기 때문에, x를 강의에서 제일 큰 5보다 작게하면, 모든 강의를 블루레이에 넣을 수 없다.
    2+2+3+4+5=16을 하면 최대 1개를 블루레이 개수로 만들 수 있다. 그 이상으로 크게 잡는 것은 의미가 없다. 왜냐하면 x의 최소를 찾는 것이기 때문

    무식하게 풀어보면
    x=2 -> [2 / 2] => 불가능
    x=3 -> [2 / 2 / 3] => 불가능
    x=4 -> [2,2 / 3 / 4] => 불가능
    x=5 -> [2,2 / 3 / 4 /5] => 4개
    x=6 -> [2,2 / 3 / 4/ 5] => 4개
    x=7 -> [2,2,3 / 4 / 5] => 3개
    x=8 -> [2,2,3 / 4 / 5] => 3개
    x=9 -> [2,2,3 / 4,5] => 2개
    x=10 -> [2,2,3 / 4,5] => 2개
    x=11 -> [2,2,3,4 / 5] =>2개
    x=12 -> [2,2,3,4 / 5] =>2개
    x=13 -> [2,2,3,4 / 5] =>2개
    x=14 -> [2,2,3,4 / 5] =>2개
    x=15 -> [2,2,3,4 / 5] =>2개
    x=16 -> [2,2,3,4 / 5] =>1개

    이 풀이법은 O(len(lectures)) * O(sum(lectures)-max(lectures))의 시간복잡도가 소요된다.
    여기서 O(len(lectures))는 각 구간 마다의 시간의 합을 계산하는 것이므로 절대로 시간을 줄일 수가 없다.
    그러면 O(sum(lectures)-max(lectures))는 최적화가 가능한지 살펴보자.
    """

    """
    3. 최적화하기
    잘 살펴보면 O(sum(lectures)-max(lectures))는 x의 "범위"다.
    그리고 추세를 살펴봤을 때, x의 크기가 작을수록 블루레이 개수는 많아지며 x의 크기가 클수록 블루레이 개수는 적어진다. 이를 성질 a라 하자.
    
    예를 들어 m=3라고 했을 때 x=9라고 잡아보자. 그런데 블루레이 크기가 2개이다. 어떻게 해야할까?
    성질 a에 의해 x = 9 ~ 16은 볼 필요가 없어진다. 블루레이 개수가 더 많은 쪽인, 8 이하인 값으로 봐야한다.

    즉, "범위"가 있으며, 특정 구간 s를 기점으로 분기가 나눠지고 있다. 그리고 조건에 맞지 않는 분기는 더 이상 볼 필요가 없어지므로 탐색 범위가
    가면 갈수록 줄어들고 있다.

    따라서 이 문제는 이분탐색 / 파라메트릭 서치라고 할 수 있다.

    최적화하면 O(len(lectures)) * O( Log (sum(lectures)-max(lectures)))
    """
    answer=math.inf

    start=max(lectures)
    end=sum(lectures)

    while start<=end:
        mid=(start+end)//2

        count=get_blueray_count(lectures,mid)

        if count>m:
            # 블루레이 개수가 m보다 많이 필요하다면, x를 너무 작게 잡은 것이다. 
            start=mid+1
        else:
            # 블루레이 개수가 m보다 적게 필요하거나 같다면, 혹시 더 작은 게 있을 수 있으므로 end 줄이기
            answer=min(answer,mid)
            end=mid-1
    
    print(answer)

if __name__=="__main__":
    main()