[알고리즘 TIL] 2343. 기타 레슨

문제

설명

이진 탐색의 중요한 점은 어떤 것을 탐색할지 정하는 것이다.

이 문제에서는 블루레이의 크기를 구하는 문제로, 블루레이의 크기를 이진 탐색으로 탐색해나가면 된다.

 

• start를 강의 길이 중 제일 큰 값, end를 모든 강의 길이의 합으로 초기화한다.
• start 와 end의 중간값인 mid를 블루레이 크기라고 가정한다.
• 블루레이 크기에 맞게 강의들을 넣고, 블루레이의 갯수와 M을 비교한다. 
  • 블루레이 갯수가 M보다 크면 요구사항에 충족하지 못하므로, start를 mid + 1로 수정한다.
  • 블루레이 갯수가 M보다 같거나 작으면, end를 mid - 1로 수정하고, answer를 mid로 갱신한다.

구현

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

answer = 0
start = max(lectures)
end = sum(lectures)

while start <= end:
    mid = (start + end) // 2
    count, total = 0,0

    # 블루레이에 강의 넣기
    for i in range(n):
        if total + lectures[i] > mid:
            count += 1
            total = 0
        total += lectures[i]
    if total:
        count += 1
    if count > m : start = mid + 1
    else: 
        end = mid - 1
        answer = mid

print(answer)