[백준-파이썬] 2343: 기타 레슨

문제로 GO !!

처음에 어떻게 풀까 하다가, 아래 '이분탐색'이라는 알고리즘 분류를 보고 힌트를 얻어서 풀었다.
'블루레이 크기'를 기준으로 삼아서 이분 탐색을 했다.
블루레이 크기의 최소는 1이고(강의 수가 1개 이상이고, 기타 강의도 자연수로 주어진다고 해서)
최대는 sum(lectures)이다. 만약에 M이 1이라고 생각하면, 하나의 블루레이에 모든 강의를 담아야 하니까 그때 크기가 sum(lectures)이다.
그래서 left =1, right= sum(lectures)를 시작으로 해서, 계속 이분 탐색을 했다.
mid를 구해서, 그 크기의 블루레이 M개로 강의를 모두 잘 담을 수 있는지 체크했다. (check 함수)

잘 담을 수 있으면, 일단 ans을 업데이트하고 더 적은 크기로 가능할 수도 있으니까 right를 바꿔줬다.
못 담으면, ans를 업데이트 하지 않고, 더 크기가 커야 하는 것이니까 left를 mid+1로 해줬다.

마지막 줄!! max(ans, max(lectures))가 정답인 것도 중요하다..!!
이걸 안해서 틀리다가, 게시판의 반례를 보고 알았다.
어떤 크기의 블루레이 M개로 강의를 잘 담을 수 있으면, 계속 ans이 업데이트 되고, 그 크기가 줄어든다.
그런데 !! 강의 동영상들 시간 중 최대값보다 짧은 블루레이 시간(크기)이 정답이 될 수는 없다.
강의 동영상을 잘라서 넣으면 안되니까.!!
ans이 강의 동영상들 시간 중 최대값보다 짧을 수도 있어서, max(ans, max(lectures))를 해줘야 맞는다.

import sys

input = sys.stdin.readline

MIIS = lambda: map(int, input().split())

N, M = MIIS()
lectures = list(MIIS())


def check(volume):  # volume 크기를 가진 블루레이 M개로 강의 모두 담을 수 있는지
    blueray_cnt = 1
    one_blueray_length = 0
    for lecture in lectures:
        if one_blueray_length + lecture > volume:
            blueray_cnt += 1
            one_blueray_length = lecture
            if blueray_cnt > M: # 블루레이가 더 필요함 = 불가능
                return False
        else:
            one_blueray_length += lecture
    if blueray_cnt > M: # 블루레이가 더 필요함 = 불가능
        return False 

    return True


left = 1
right = sum(lectures)
ans = 0

while left <= right:
    mid = (left + right) // 2  # 블루레이 크기

    if check(mid):
        ans = mid
        right = mid - 1
    else:
        left = mid + 1

print(max(ans, max(lectures)))