t_떡볶이떡만들기_201

문제

적어도 M만큼의 떡을 챙겨야함 == M이딱안맞을 수 있음

답

높이가 가장높은것기준을 end로 잡고 이진탐색을하면될듯하다.
탈출조건 : 합이 M보다 작음
햇갈린 point : 탈출조건일때 Return값을 end를 줘야하나
탈출조건에 갔다는건 딱 맞는 값을 못 찾았다는것.
그렇다고 하면 start는 만족하는값을 충족시키지못하고 end는 만족하는값을 넘는 값이다. therefore end를 리턴해줘야함
실전에서는 실수를 줄이기 위해서 떡양이 충분할때 계속 result값에 기록하는 편이 좋을 듯.

import sys

n, m = map(int, sys.stdin.readline().strip().split())
arr = list(map(int, sys.stdin.readline().strip().split()))

def cal_sum(v):
    sum = 0
    for a in arr:
        tmp = a - v
        if tmp>0:
            sum +=tmp
    return sum

# <span id="end-"></span>end 
def search(start,end):
    if start>end:
        return end
    mid = (start+end)//2
    sum = cal_sum(mid)
    if m == sum :
        return mid
    elif m < sum:
        # sum이 크다 = 자르는 길이가 작다
        return search(mid+1,end)
    return search(start,mid-1)

print(search(0,max(arr)))