2343번 기타 레슨

https://www.acmicpc.net/problem/2343

약간 애착이 가는 문제이다.
어제 풀려다가 방법이 생각 안나서 그냥 누웠는데
자기 전에 고민하다가 생각나서 녹음해놓고 다시 잤다.

아이디어

이분탐색 돌 때, 동영상 길이를 합치면서 mid 초과가 되면 다른 묶음으로 처리하고 마지막에 만들려는 블루레이 수(m)와 비교

한 번 틀렸던 이유는 내가 만든 묶음(cnt)와 블루레이(m) 비교할 때 cnt가 더 적게 나와도 정답이 될 수 있다. 나는 처음에 무조건 같아야지 정답 되는 줄 알았다가 틀렸다.

그리고 굳이 low=1부터 시작할 필요없고 어차피 만들 수 있는 블루레이 시간 중 최솟값이니까 low = max(record)로 해도 충분하다 이것보다 작을 수는 없으니까!

코드

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

low = max(record) # 굳이 시작을 1부터 할 필요가 없음
high = sum(record)
answer = 0

while low <= high:
    mid = (low + high) // 2
    cnt = 1 # 블루레이 묶음 수
    sum = 0 # 합
    
    for num in record:
        if sum + num <= mid:
            sum += num
        else:
            sum = num
            cnt += 1

    if cnt <= m: # 블루레이가 m보다 적게 나왔을 때도 정답이 될 수 있음
        high = mid - 1
        answer = mid
    elif cnt > m:
        low = mid + 1

print(answer)