[Algorithms] 결정&그리디 알고리즘-뮤직비디오(결정 알고리즘)

 

• 최소 용량의 크기를 이분 탐색으로 찾아나가자 
• DVD 한 장에 들어갈 수 있는 용량은 최소 9분 (가장 긴 노래의 용량)에서 최대 (1+2+3..+9=45)분이다 
• 따라서 Left Pointer는 9분, Right Pointer는 45분에서 mid 값을 찾아서 이분 탐색을 진행한다 
• 곡의 순서가 그대로 유지되어야 함을 인지해야 한다 
• 사업에 낭비되는 DVD를 가급적 줄이려고 하기 때문에, M개 이하이여도 (즉, 2개, 1개) 괜찮다 

import sys
 
# sys.stdin = open("input", "rt")
n, m = map(int, input().split())
song = list(map(int, input().split()))
 
def count(mid):             # 총 나눠지는 DVD의 숫자를 반환한다
    cnt=1                   # DVD 는 최소 1개부터 시작한다
    total=0
    for x in song:
        if total+x > mid:   # 노래의 시간을 더했을때
            cnt+=1          # 주어진 용량을 초과하면
            total=x         # 이전 차례의 용량까지 하나의 DVD로 만든다
        else:
            total+=x        # 용량을 초과하지 않았으면 계속 더해준다
    return cnt
 
 
lt=max(song)                # 가장 긴 노래의 용량
rt=sum(song)                # 1+2+...+9 분의 최대 노래 길이
res=0
while lt<=rt:
    mid=(lt+rt)//2
    if count(mid)<=m:
        res=mid
        rt=mid-1
    else:
        lt=mid+1
print(res)