[BOJ] 기타 레슨

---

코드

import sys
input = sys.stdin.readline

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

start = max(nums)
end = sum(nums)
ans = []

while start <= end:
    mid = (start + end) // 2
    tmp = 0
    bnum = 1    # 블루레이 개수
    i = 0
    while i < n:
        if bnum > m:
            break
        if tmp + nums[i] <= mid:
            tmp += nums[i]
            i += 1
        else:
            bnum += 1
            tmp = 0
            
    if bnum > m:
        start = mid + 1
    elif bnum <= m:
        end = mid - 1

print(start)

결과

풀이 방법

• 이분탐색을 활용하였다.
• start 값은 가장 시간이 긴 강의시간으로, end 값은 총 강의시간으로 초기화하였다.
• mid 분량의 블루레이가 몇 개 나오는지 카운트하여 bnum에 기록하고, 개수가 M개를 넘으면 더 카운트할 필요가 없기 때문에 break로 탈출하게 하였다.
• bnum 개수가 M보다 크면 블루레이 크기를 늘리기 위해 start 값을 mid + 1로 설정하고, M보다 작거나 같으면 end 값을 mid - 1로 설정한 후 재탐색하도록 하였다.

---