baekjoon 2343: 기타 레슨

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

2343번: 기타 레슨

---

이진탐색 문제로, 기존 이진탐색에 나누어지는 덩어리의 갯수(내 코드에선 t)에 맞추어 최댓값을 구하는 문제이다.

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

st = max(arr)
ed = sum(arr)
while st <= ed:
    mid = (st+ed)//2

    t = 0
    b = 0
    for i in range(n):
        if b + arr[i] > mid:
            t+=1
            b = 0
        b += arr[i]
    # b가 mid값보다 커지진 않았지만 존재할 경우
    if b:
        t+=1

    if t > m:
        st = mid +1
    else:
        ed = mid -1
print(st)