문제를 풀기 앞서 이진탐색에 대해 알아보자.

🌟이진탐색

이진 탐색(binary search)은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도는 O(logN)

이진탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.

이진 탐색 과정

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

---

문제

백준 - 기타 레슨

예제 입력1

9 3
1 2 3 4 5 6 7 8 9

예제 출력1

17

---

풀이

블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 한다는 점에서 이진 탐색 알고리즘을 선택하는 것이 낫다고 생각했다.

1. 이진 탐색의 시작 인덱스는 최대 길이의 레슨이고, 종료 인덱스는 모든 레슨 길이의 합 ( 시작 인덱스 = 9, 종료 인덱스 = 45)
2. 블루레이 개수가 3일 때, 9~45 사이에서 블루레이 크기의 최솟값을 이진탐색으로 찾아야 한다.

이진 탐색 수행

• 중앙값 크기로 모든 레슨을 저장할 수 있으면
  종료 인덱스 = 중앙값 - 1 # 왼쪽 데이터셋
• 중앙값 크기로 모든 레슨을 저장할 수 없으면
  시작 인덱스 = 중앙값 + 1 # 오른쪽 데이터셋

코드

# 기타 레슨

N, M = map(int, input().split())
lecture = list(map(int, input().split(' ')))

start = 0
end = 0

for i in range(N):
    if start < lecture[i]:  # 최대 길이의 레슨
        start = lecture[i]
    end += lecture[i]  # 모든 레슨 길이의 합

while start <= end:
    middle = int((start + end) / 2)
    count = 0
    sum = 0

    for i in range(N):
        if sum + lecture[i] > middle:
            count += 1
            sum = 0  # 초기화
        sum += lecture[i]

    if sum != 0:
        count += 1

    if count > M:
        start = middle + 1
    else:
        end = middle - 1

print(start)