[BinarySearch] 기타 레슨

출처: deok2kim.tistory.com/109

[python] 백준 - 2343. 기타 레슨

 

# 2343 guitar lesson
def add_lesson():
    cnt = 0  # 레코드 갯수 세기
    sum_lesson = 0  # 한 레코드에 들어갈 레슨들의 합
    for i in range(N):
        if sum_lesson + lesson_list[i] > mid:
            cnt += 1
            sum_lesson = 0

        sum_lesson += lesson_list[i]
    else:
        if sum_lesson:
            cnt += 1
    return cnt


if __name__ == "__main__":
    N, M = map(int, input().split())  # N: 레슨 수, M: 블루레이 수
    lesson_list = list(map(int, input().split()))  # 레슨들

    right = sum(lesson_list)   # 레슨을 하나의 레코드에 다 담을 수 있을 때 레코드의 크기는 레슨의 합이다
    left = max(lesson_list)  # 레코드가 가질 수 있는 가장 작은 크기
    while left <= right:
        # 레코드 크기 중간값 구하기
        mid = (left + right) // 2
        cnt = add_lesson()
        if cnt <= M:  # 레코드 숫자가 모자라면 레코드 크기(mid)를 줄인다.
            right = mid - 1
        elif cnt > M:  # 레코드 숫자가 더 많아지면 레코드 크기(mid)를 늘린다
            left = mid + 1

    # 답은 left 에 있다. (최소 크기)
    print(left)

if __name__ == '__main__':
    n, m = map(int, input().split())
    lesson = list(map(int, input().split()))
    start, end = max(lesson), sum(lesson)

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

        cnt = 0
        play_time = 0
        for l in lesson:
            # play_time이 m보다 커지면 새로운 dvd 필요
            if play_time + l > mid:
                cnt += 1
                play_time = 0

            play_time += l

        cnt += 1 if play_time else 0

        if cnt <= m:
            end = mid - 1
        else:
            start = mid + 1
    print(start)