떡복기 떡 만들기 이진 탐색

나의 풀이 

def bs(arr, start, end, wanted):
    if end == start:
        return arr[start]
    mid = (start + end) // 2
    
    total = 0
    for i in range(len(arr)):
        dok = arr[i] - arr[mid]
        if dok <0:
            dok = 0
        total += dok
    if total == wanted:
        return arr[mid]
    if total > wanted:
        bs(arr, mid+1, end, wanted)
    else:
        bs(arr, start, mid-1, wanted)

n, k = map(int, input().split())
doks = list(map(int, input().split()))
result = bs(doks, 0, n-1, k)
print(result)

정답

    # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
    n, m = list(map(int, input().split(' ')))
    # 각 떡의 개별 높이 정보를 입력받기
    array = list(map(int, input().split()))

    # 이진 탐색을 위한 시작점과 끝점 설정
    start = 0
    end = max(array)

    #이진 탐색 수행(반복적)
    result = 0
    while(start <= end):
        total = 0
        mid = (start + end) // 2
        for x in array:
            # 잘랐을 때의 떡의 양 계산
            if x > mid:
                total += x - mid
        # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
        if total < m:
            end = mid - 1
        # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
        else:
            result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
            start = mid + 1
    # 정답 출력
    print(result)

정답을 통해 나의 풀이가 잘못 된 것을 깨달았다. 나는 단순하게 배열을 이진 탐색해서 구할 생각을 하였는데

생각해보니 떡의 길이를 이진 탐색을 하는게 맞는거 같다.