2343 기타레슨 이분탐색

실1

어느정도 이분탐색에 감이 잡혔다.

하지만 골드급으로 가면 의미 없겠지....

이번 문제는 공유기 설치 문제를 풀고 나면 조금 더 쉽게 감이 잡히는 문제이다.

가장 먼저 해야할 것은 이 문제가 탐색 문제인지 확인하는 것이다.

일단 최소값을 찾아내라 했으니 탐색문제인데 완전탐색으로 가능할지 확인해야 한다.

완전탐색으로 진행할 경우 블루레이의 크기(최대 10000 * 100000) 를 모두 탐색하면서 레슨의 조합을 찾아(블루레이의 개수 만큼) 그 중에서 최소값을 찾아내는 작업을 해야하는데,

시간복잡도가 그냥 넘어버릴 것 같다.

때문에 이분탐색을 통해 푸는게 맞다.

먼저 이분탐색에서의 핵심은 내가 탐색하려는 대상이 무엇인지 명확하게 확인하는 것이 중요하다.

이것을 확인하고 비교대상을 찾아 비교를 통해 계속해서 가장 답에 가까이 다가가는 것이 핵심이다.

현재 문제에서 찾아야되는 대상은 블루레이의 최소 크기이다.

블루레이 크기의 범위는 현재 모든 레슨의 합이고 최소는 레슨의 최대 크기이다.

이 사이에서 이진탐색을 하면서 블루레이의 최소 크기만큼 만들어낼 수 있는 블루레이의 개수를 세어주고, 개수가 M보다 작다면 최소크기를 더 줄이고, 개수가 크다면 최소크기를 늘려서 답을 찾아가야한다.

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


def solution():
    start = max(lessons)
    end = sum(lessons)

    return binary_search(start, end)

def binary_search(start, end):
    mid = (start + end) // 2
    count = find_blueray(mid)

    if start > end: 
        return start

    if count > m:
        return binary_search(mid+1, end)
    else:
        return binary_search(start, mid-1)


def find_blueray(mid):
    start = 0
    count = 0
    for i in range(len(lessons)):
        if start + lessons[i] > mid:
            # 단위 크기와 같으면
            count += 1
            start = 0
        start = start + lessons[i]
    if start != 0: # 마지막에 카운트하나를 더해주는 과정이 필요
        count += 1
    return count

print(solution())