07-3. 떡볶이 떡 만들기

1. 순차 탐색 -> 시간오류 날 것.. 

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

data = sorted(data,reverse=True)

l = data[0]
sum = 0 
while sum < m :
  sum = 0 
  for i in data:
    if l-i <= 0 : 
      pass
    else :
      sum += l-i 

print(sum)

 

2. 파라메트릭 서치 -> 이진탐색 

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

start = 0 
end = max(data)

result = 0 
while start<= end:
  sum = 0 
  mid = (start + end) //2 

  for i in data:
    if i > mid :
      sum += (i-mid)
    
  if sum < m : 
    end = mid -1 
  else : 
    result = mid
    start = mid +1 

print (result)