[알각코] 인프런 4-3 뮤직비디오 (결정알고리즘)

뮤직비디오 (결정알고리즘)

문제 정보는 인프런의 파이썬 알고리즘 문제풀이 코딩테스트에 있습니다!

문제풀이

import sys
sys.stdin = open("input.txt", "r")

def count(capacity):
  cnt=1
  sum=0
  for x in music:
    if sum+x>capacity:
      cnt+=1
      sum = x
    else:
      sum+= x
    return cnt

n, m = map(int, input().split())
music = list(map(int, input().split()))
maxx=max(music)
lt=1
rt=sum(music)
res = 0

while lt<=rt:
  # dvd 저장용량
  mid=(lt+rt)//2
  if mid>=maxx and count(mid)<=m:
    res=mid
    rt = mid-1
  else:
    lt=mid+1

print(res)