완전탐색 - 여러 구간, 구간 합의 최댓값이 최소가 되도록

n개의 숫자가 주어지면, 숫자 사이에 칸막이를 m - 1개 두어 총 m개의 구간으로 나누려고 합니다. 이때 칸막이를 적절하게 설치하여, m개의 구간으로 나누어 졌을 때 구간 합들 중 최댓값이 최소가 되도록 하라.

 

입력 예제 

6 3 (n m) 

7 2 1 5 6 3

 

출력: 9

-> 7 2 | 1 5 | 6 3 과 같이 나누면 구간 합 중 최댓값이 9

 

100 개의 숫자를 여러 개의 구간으로 나누는 경우의 수, 숫자들을 모든 구간으로 나누어 완전 탐색 시

최악의 경우 99C50 = 약 5*(10**28) 이므로, 너무 많은 수. 

 

solution

구간의 합의 최댓값을 결정하여 그 최댓값에 맞게 구간을 나눈다. 

숫자를 순서대로 탐색하며 현재 숫자에 바로 전 숫자를 더한 값이 설정한 최댓값 보다 크면, 다음 구간으로 이동시킨다. 

만약, 숫자 하나가 설정한 최댓값보다 크면 구간을 나눌 수 없는 경우이다. 

 

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

#m개의 구간...이 아니라 구간 합의 최댓값으로 탐색
ans=10000
for i in range(1,10001):
    # possible : 구간을 나눌 수 있으면 true
    # section : 나뉘어져야 하는 구간의 개수
    possible = True
    section = 1
    
    cnt=0
    for j in range(n):
        if arr[j] > i :
            possible=False
            break
        if cnt+arr[j] > i :
            cnt=0 # 다음 구간
            section+=1
        #이번 구간에 j숫자 넣음
        cnt+=arr[j]

    if possible and section <= m:
        ans=min(ans,i)

print(ans)