728x90
2343번: 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
분석
뮤직비디오 (이분탐색, 결정 알고리즘)
문제 DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 순서가 그대로 유지되어야 한다. 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 하였다. DVD
karla.tistory.com
풀이
n,m=map(int,input().split())
a=list(map(int,input().split()))
start=end=0
for i in a:
if start<i:
start=i # 레슨 최대값을 시작 인덱스로 저장
end+=i # 모든 레슨의 총합을 종료 인덱스로 저장
while start<=end:
mid=int((start+end)/2)
tmp=0
cnt=0
for i in range(n):
if tmp+a[i]>mid: # 현재 블루레이에 저장 할 수 없어 새로운 블루레이로 교체
cnt+=1
tmp=0
tmp+=a[i]
if tmp!=0: # 마지막 블루레이가 필요하므로
cnt+=1
if cnt>m:
start=mid+1
else:
end=mid-1
print(start)
728x90