baekjoon 2512: 예산

https://www.acmicpc.net/problem/2512

---

이진탐색 문제로, 최댓값을 빠르게 구하는 문제이다.

 

예산내의 최댓값을 구하기 위해 임의로 정해진(mid) 값에 대비하여 값을 더한 후, 최소값(st)과 최댓값(ed)의 범위를 줄여가는게 포인드이다.

n = int(input())
arr = list(map(int,input().split()))
budget = int(input())

st = 0
ed = max(arr)

while st <= ed:
    mid = (st + ed)//2

    target = 0
    for i in range(n):
        if arr[i] - mid >=0:
            target += mid
        else:
            target += arr[i]
    if target <= budget:
        st = mid +1
    elif target > budget:
        ed = mid -1

print(ed)