2343_기타레슨_(python)

 처음에 코드를 봤을 때 떠올렸던 알고리즘은 완전탐색이었고 조합을 생각했었지만 시간초과가 나올 것 같아서 바로 이분탐색으로 생각을 전환했다. mid 값을 무엇으로 정해야하며 mid가 정해진 기준으로 무엇이 left,right를 어떻게 움직여야 할지 많이 고민했다. 고민을 2일 정도 한 결과 블루레이의 길이를 기준으로 하자하고 코드를 작성했지만 53%로에서 계속 틀렸다고 나왔다. 더 이상 고칠 게 없을 것 같아서 다른 사람들의 코드를 보았지만 별반 차이가 없는 것 같아서 반례를 찾아보았다. 7 6
100 400 300 100 500 101 400 이라는 반례를 찾았다.

 글쓴이는 left를 테스트케이스만 보고 리스트의 끝 값을 넣어뒀다. 여기서 문제를 잘 읽어야한다. 문제에서 강의 순서별로 길이를 제공한다 했지 길이 순서대로 제공한다고 하지 않았기 때문에 가장 큰 값이 어디에도 있을 수 있다. 

n,m = map(int,input().split()) # n 강의의 수 m개의 블루레이
data = list(map(int,input().split())) # data를 입력받는다.
left,right = max(data),sum(data) # 최소는 data길이중 최대이고 최대는 data총합 길이만큼만 들어갈 수 있다.
result = 0 # 결과값은 0이다.

while left <= right: # left가 right보다 작거나 같은 동안
    mid = (left + right) // 2 
    cnt = 1
    flag = 0
    tempsum = 0 #tempsum은 계속 0으로 초기화 될 것임
    for i in range(len(data)):
        tempsum += data[i] # tempsum에 data[i] 값을 넣어준다.
        if tempsum > mid: # tempsum이 현재 블루레이 길이보다 크다면
            tempsum = data[i] # tempsum에다가 data[i]를 넣는다.
            cnt += 1 # 블루레이 갯수를 하나 증가시켜준다.
            if cnt > m: 
                left = mid+1
                flag = 1
                break
    if flag == 0:
        result = mid
        right = mid - 1

print(result)