[백준] 2343번 기타 레슨 ★

💡문제접근

• 이분탐색을 사용했는데 한 가지를 간과해서 많은 시간이 걸렸던 문제였다.
• 바로 start와 end의 값을 지정하는 부분에서 문제가 발생했던 것이다. 처음에는 start의 값을 리스트의 최소값, end의 값을 배열 전체의 합으로 넣었는데 이렇게 되면 문제가 발생하는데 다음 반례를 통해서 설명이 가능하다.

💡반례

7 6
100 400 300 100 500 101 400

만약 start의 값을 100으로 놔두면 이분 탐색에 의해 mid의 값이 갱신이 되는데 그렇게 갱신이 되어 mid의 값이 커지게 되면 start의 값도 커지게 된다. 그렇게 된다면 바뀐 start의 값보다 작은 값이 블루레이 디스크에 들어갈 수 없으므로 길이의 최댓값을 start로 넣어야 문제가 발생하지 않게 되는 것이다.

💡코드(메모리 : 42204KB, 시간 : 744ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
length = list(map(int, input().strip().split()))
answer = 0

start = max(length)
end = sum(length)
while start <= end:
    mid = (start + end) // 2
    cnt, Sum = 0, 0
    for i in range(N):
        if Sum + length[i] > mid:
            cnt += 1
            Sum = 0
        Sum += length[i]

    if Sum > 0:
        cnt += 1

    if cnt > M:
        start = mid + 1
    else:
        end = mid - 1
        answer = mid
print(answer)

💡소요시간 : 41m