뮤직비디오

생성일: 2022년 1월 14일 오후 5:27

구현 코드

# 뮤직비디오(결정 알고리즘)
import sys
sys.stdin = open("input.txt", "rt")

def Count(capacity):
    sum = 0
    cnt = 1
    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:
    mid = (lt+rt)//2
    if mid >= maxx and Count(mid) <= m:
        res = mid
        rt = mid - 1
    else:
        lt = mid + 1

print(res)

• 이분탐색을 활용한다.(결정 알고리즘)
  • 가능한 dvd의 최소 용량은 1부터 노래들을 전부 한 dvd에 담은 sum(music) 까지이다.
  • 이 구간을 절반으로 나눠가며 확인한다.
• Count 함수는 특정 capacity(용량)인 dvd들에 노래들을 담을 때 몇개의 dvd가 필요한지 구하는 함수이다.