문제

강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 레슨의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

코드

n, m = map(int, input().split())
lesson = list(map(int, input().split()))
bags = n//m

sizes = list()
cnt = 0
left = sum(lesson)//m
right = sum(lesson)
answer = right
while left <= right:
    mid = (left+right) //2
    if mid < max(lesson):
        left = mid+ 1
        continue
    sum = 0
    cnt = 1
    for i in range(len(lesson)):
        if lesson[i] > mid:
            break
        elif sum + lesson[i] <= mid:
            sum += lesson[i]
        else:
            sum = lesson[i]
            cnt += 1

    if cnt <= m:
        answer = min(answer, mid)
        right = mid - 1
    else:
        left = mid + 1


print(answer)

설명

이분탐색은 정렬을 하고 사용하는 것이 당연하다는 듯이 문제도 제대로 안 읽고 정렬을 한 상태로 문제를 풀려고 했다가 시간 낭비를 엄청나게 했다. 이분탐색의 기준을 블루레이의 크기로 잡고 최소는 입력된 레슨 크기의 평균, 최대는 레슨 전체의 합이다. 이것을 이용해서 이분탐색을 진행하면 되는 문제였다. 문제만 제대로 읽었어도 금방 풀었을 것 같다. 문제를 천천히, 꼼꼼히 읽자...