[Python] 2512번 예산

✏️ 문제

문제 파악

이분 탐색으로 푸는 거의 대표적인 문제!! 

 

알고리즘

• 매개 변수 탐색
• 이분 탐색

 

 

코드

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

if (sum(req) <= m):
  print(max(req))
else:
  start, end = 1, max(req)
  
  while start <= end:
    mid = (start+end) // 2
    use = 0

    for i in range(n):
      if mid >= req[i]:
        use += req[i]
      else: 
        use += mid
    
    if use > m:
      end = mid - 1
    else:
      start = mid + 1

  print(end)