알고리즘 스터디 - 백준 2343번 : 기타 레슨

문제 해석

• 블루레이 안에 N개의 강의가 존재하고 강의의 순서가 바뀌면 안됨
• i 번 강의와 j 번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 블루레이에 녹화해야함
• 블루레이의 개수를 줄이려 M개의 블루레이에 모든 강의 동영상을 녹화하려하고 모두 같은 크기임
• 각 강의의 길이가 분으로 주어질 때 블루레이의 크기 중 최소를 구하는 프로그램을 작성해야 함

어떤 알고리즘을 써야할까?

1. 강의의 수 N, 블루레이의 개수 M
2. 강의 순서대로 강의 길이가 주어짐

9 3
1 2 3 4 5 6 7 8 9
>>> 17

모든 강의 길이의 합 = 45인데 왜 블루레이 크기 중 최소가 17일까? 1, 2, 3, 4, 5가 1번이고 6, 7이 2번이고 8, 9가 3번인데 크기가 각각 15, 13, 17이라 17 밑으로는 블루레이 크기가 될 수 없기에 최솟값이 17이 된다.

기존 이진탐색 알고리즘을 살펴보자.

def binary(array, target):
    left, right = 0, len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] < target:
            left = mid + 1
        elif array[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

여기서 left, right를 정의하는 과정에서 시작해야하는 값과 가장 큰 값을 정의해야 해줘야 한다. 만약 시작을 해야한다면 적어도 2개 이상 서로 더하지 않고 길이 중 가장 큰 값을 left로 하고 right를 전체 길이의 합으로 정의를 하게 되면 다음과 같이 나오게 된다.

알고리즘 코드

N, M = map(int, input().split())

length = list(map(int, input().split()))

left, right = max(length), sum(length)

answer = 0

while left <= right:
    mid = (left + right) // 2
    current_total = 0
    current_count = 0

    for i in length:
        if current_total + i > mid:
            current_count += 1
            current_total = i
        else:
            current_total += i
    
    if current_count <= M - 1:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)