BaekJoon2512_예산

문제

풀이

우선 입력값이 n부터 100만 사이이다. 시간제한은 1초 이내이므로 탐색 중에서 이분탐색을 떠올렸다.
start는 0부터 end는 신청 예산중 제일 높은 금액을 할당한 뒤 전형적인 이분탐색을 진행하면 답을 구할 수 있다.

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
city = list(map(int,input().split()))
total_money = int(input())

city.sort()
start = 0
end = max(city)

while start <= end:
    mid = (start+end) // 2
    check = 0
    for i in city:
        if i > mid:
            check += mid
        else:
            check += i
    if check <= total_money:
        start = mid + 1
    else:
        end = mid - 1
        
print(end)