백준 2512 - 예산 ( Python )

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

2512번: 예산

이진 탐색으로 풀이가 가능하다

 

예산의 상한선을 구하는 문제다

예산의 상한선을 구하기 위해서는 총 예산의 최적의 합계가 필요하다.

 

이진 탐색의 중간값이 예산의 상한선이 되며

해당 상한선보다 예산이 큰 경우에는 상한선을 더하고

예산이 작거나 같은경우에는 해당 예산을 더한다

 

총 예산의 합이 지정된 예산값보다 작거나 같은 경우 상한선을 높이고

-> start값을 늘려줌

초과된 경우에는 상한선을 줄이는 방식을 반복해서 이어간다.

-> end값을 줄여줌

 

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

array.sort()

start = 0
end = max(array) #국가의 예산보다 큰 예산은 배정되지않음

while start <= end:
    sum = 0
    mid = (start + end) // 2 # 이진탐색을 위한 중간값
    for i in array: # 국가의 예산을 순회하면서 총합을 계산
        if i <= mid: # 중간값보다 작거나 같은경우는 원래 예산을 더함
            sum += i
        else: # 중간값이 더 큰 경우에는 중간값을 더함
            sum += mid
    if sum <= budget: # 합산된 예산이 지정된 예산보다 같거나 작은 경우
        start = mid +1 # start 예산보다 +1 한 예산으로 중간값 다시 계산
    else: # 예산이 초과된 경우
        end = mid - 1 # end 예산보다 -1 한 예산으로 중간값 다시 계산
print(end) # 가장 큰 값을 출력해야하므로 end 값 출력