문제

입력 , 출력

solution

import sys

input = sys.stdin.readline


def find_number(start, end):
    while start <= end:
        cur = 0
        mid = (start + end) // 2
        for i in arr:
            if i > mid:
                cur += mid
            else:
                cur += i
        if cur <= m:
            start = mid + 1
        else:
            end = mid - 1
    return end


n = int(input())
arr = list(map(int, input().split()))
m = int(input())
a = find_number(0, max(arr))
print(a)

설명

이분탐색으로 총합이 m보다 작을경우 start 를 mid+1
m보다 클경우는 end를 start-1 을 해서 이분탐색을 한다

후기

이분탐색을 오랜만에 할려고 하니까 손이 안갔다..
arr배열을 정렬하고 가장 작은원소 , arr[0] 부터 max(arr) 까지 중에서 탐색을 했는데
50%에서 계속 틀렸다고 나왔다.
반례를 계속 못찾았는데
배정된 예산이 입력값보다 작은경우를 생각을 못했던것 같다.
그래서 0을 넣으니까 성공...

반례를 못찾아서 빨간줄이...