[백준] 2343번: 기타 레슨

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

initial

i really couldnt solve it for 2 hours

my wrong sol

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

left, right = max(lst), sum(lst)
real=0
while left<right:
    ans= 0
    mid = left+(right-left)//2
    tmp = 0
    for i in lst:
        if tmp+i>=mid:
            ans+=1
            tmp=0
        tmp+=i
    if tmp!=0:
        ans+=1
    # for i in lst:
    #     tmp+=i
    #     if tmp>=mid:
    #         ans+=1
    #         tmp=i
    # if tmp!=0:
    #     ans+=1
    if ans<=m:
        real=mid
        right=mid
    else:
        left=mid+1
print(real)

sol

very close. If we add tmp+i and is equal to mid, then it is still valid like we can add this current item and its a valid case. So it should be

    for i in lst:
        if tmp+i>mid:
            ans+=1
            tmp=0
        tmp+=i

so

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

left, right = max(lst), sum(lst)
real=0
while left<right:
    ans= 0
    mid = left+(right-left)//2
    tmp = 0
    for i in lst:
        if tmp+i>mid:
            ans+=1
            tmp=0
        tmp+=i
    if tmp!=0:
        ans+=1
    if ans<=m:
        right=mid
    else:
        left=mid+1
print(left)

complexity

so the outer while loop goes on for log(sum(lst) - max(lst)) and inner for loop is n so it is log(sum(lst)-max(lst))*n

space is n