[백준] 2343번 - 기타 레슨 (파이썬)

https://www.acmicpc.net/problem/2343

# 기타 레슨

N, M = map(int, input().split())
arr = list(map(int, input().split()))

answer = 0
left, right = max(arr), sum(arr)
while left <= right:
    mid = (left+right)//2

    # 블루레이에 강의 넣기
    count, sum = 0, 0
    for i in range(N):
        if sum + arr[i] > mid:
            count += 1
            sum = 0
        sum += arr[i]
    if sum:
        count += 1

    if count > M:
        left = mid + 1
    else:
        right = mid - 1
        answer = mid

print(answer)

 

이분탐색
1. left는 동영상 길이의 최솟값, right은 동영상 길이의 최댓값
2. 이분탐색
    - 강의를 순서대로 블루레이에 넣는다. 길이는 mid
    - 강의를 넣고 나온 블루레이의 개수가 M보다 크다면 left = mid +1
    - M보다 작으면 right = mid + 1, answer = mid
3. answer 출력

 

문제를 이해하는데 고생했다.

강의의 순서가 바뀌면 안된다 -> 블루레이에 강의를 넣을 때, 순서대로 넣어야 한다.

블루레이 크기를 최소화 -> 구해야 하는 값

M개의 블루레이 -> M개 이하의 블루레이를 사용할 수 있다.