2343: 기타레슨

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

예제 입력 1 복사

9 3
1 2 3 4 5 6 7 8 9

예제 출력 1 복사

17

 

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

 

순서대로 저장해야 하므로 브루트포스하게 집합을 확인할 수 있습니다.
한 집합에 포함된 개수를 기준으로 조건을 돌립니다. 

이진탐색을 계속 돌리면서 mid 현재 최대집합보다 작은 부분집합을 만들도록 하고, 부분 집합 개수가 입력값보다 크면 현재 최대 집합을 변경합니다.

이진탐색을 돌리면 mid로 최대집합을 찾을 수 있고, 현재 최대집합을 조건과 비교할 수 있습니다.

여기서는 비교되는 값으로 부분집합의 총합이 들어갑니다. 

while문 1회 안에서 mid값은 고정되어 있으므로 현재 최대집합값mid보다 작은 부분 집합을 만들고, 부분집합 개수를 업데이트해 조건을 비교할 수 있게 합니다.

최대집합의 요소합(mid)이 작아지면 부분집합의 개수가 늘어나므로 부분 집합의 개수가 input값을 넘어가면 최대 집합의 요소합mid을 증가시킵니다.
 (1,2,3,4,5) (5,6,7) (8,9) -> (1,2,3,4) (5,6)(7)(8)(9)

#블루레이를 m개로 나누어야 한다.(최소가 아닌 조건)
# n개의 블루레이 합의 최소를 구해야 한다. (최소 찾기)
#결론적으로 최대 집합의 합이 최소가 되는 것을 구해야 합니다.

n,m= map(int, input().split())
blueray = list(map(int, input().split()))
answer=0

start = max(blueray) #1개씩 집합을 만들었을 때 최댓값이 최대 집합의 가장 작은 값
end = sum(blueray)


while(start<=end):
    #하나의 집합이 하면 최소가 아니면, 집합 개수를 늘린다.
    mid = (start+end)//2 #현재 최대 집합의 합
    setSum =1  #한 세트당 요소의 개수
    bluesum =0  #여러 집합 중최대집합의 합
        
    #순서대로 저장해야 하므로 브루트포스하게 집합을 확인할 수 있습니다.
    #한 집합에 포함된 개수를 기준으로 돌아갑니다.
    # (1,2,3,4,5) (5,6,7) (8,9) -> (1,2,3,4) (5,6)(7)(8)(9)
    for b in blueray: #최대 집합의 합 구하기
        if(bluesum+b>mid): #새로운 블루레이에 담기
            bluesum=b 
            setSum+=1
        else:
            bluesum += b
    

    if setSum <= m:
        answer = mid  # 가능한 최소 블루레이 크기 저장
        end = mid - 1  # 더 작은 크기로 탐색
    else:
        start = mid + 1  

print(answer)