[백준/Python] 2343 기타 레슨

문제 링크

2343번: 기타 레슨

 

문제 풀이

• 블루레이는 수가 m개이면서 용량이 최소여야 한다. 이 때, 모든 강의 영상이 최소 하나씩은 담기게 되므로, 블루레이의 크기는 가장 용량이 큰 강의 영상보다 같거나 커야 한다. 또한, 전체 강의 영상의 용량을 합한 것보다 클 수는 없다. 따라서 이분 탐색의 시작점을 가장 용량이 큰 강의 영상(max(l))로 지정하고, 끝점을 전체 강의 영상의 용량(sum(l))로 지정해야 한다.
• 기준점(mid)이 정해지면, 해당 크기의 블루레이에 얼만큼의 강의 영상이 들어갈 수 있는지와 필요한 블루레이 개수를 세야 한다. 블루레이의 개수가 만약 정해진 개수(m) 보다 크다면 용량이 작아 더 많은 양의 블루레이가 필요하므로 기준점을 늘려야 하고, 그렇지 않다면 블루레이 개수가 적거나 같으므로 해당 값을 비교하여 더 작은 값을 저장하도록 한다.

 

전체 코드

import sys

n, m = map(int, sys.stdin.readline().split())
l = list(map(int, sys.stdin.readline().split()))

start = max(l)
end = sum(l)

res = sum(l)
while start <= end:
    mid = (start + end) // 2
    total = 0
    count = 1
    for i in l:
        if total + i <= mid:
            total += i
        else:
            count += 1
            total = i
    if count > m:
        start = mid + 1
    else:
        res = min(res, mid)
        end = mid - 1

print(res)