[이분탐색(결정알고리즘)][그리디 알고리즘] - 뮤직비디오(결정 알고리즘)

문제

주어진 뮤직비디오를 m개로 나눠서 사용할 때 최소 길이로 맞출 수 있는 방법을 풀어라

(m개보다 갯수가 작아도 되나 그렇게 되면 최소 길이라는 조건이 충족되지 않음)

문제 풀이 - 1

def Count(mid):
    s = 0
    cnt = 1
    for i in music:
        if s + i > mid:
             cnt += 1
             s = i
        else:
            s+=i
    return cnt

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

lt = 1
rt = sum(music)
res = 0

while lt <= rt:
    mid = (lt+rt)//2
    if Count(mid) <= m:
        res = mid
        rt = mid - 1

    else:
        lt = mid +1
print(res)

문제 풀이 - 2

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

start = 1
end = sum(music)
res = 0

while start <= end:
    mid = (start+end)//2
    s = 0
    cnt = 1
    for i in music:
        if s + i > mid:
            s = i
            cnt += 1
        else:
            s += i
    if cnt <= m:
        end = mid - 1
        res = mid
    else:
        start = mid + 1
print(res)

• 해당 문제는 리스트 안에 주어진 뮤직비디오 길이를 돌아가며 mid값을 넘어갈 때 1개의 묶음으로 본다. 그렇기에 cnt를 1씩 증가시켜주고 반복문이 끝났을 때 해당 뮤직비디오의 갯수가 m개를 넘어가면 범위를 조금 늘려 다시 확인하고 m보다 작으면 범위를 좁혀 다시 확인하는 식으로 풀어야 한다.