•binary search 이용하기
low과 high boundary를 이용해서 midpoint와 low, 또는 midpoint와 high를 비교한 후 value를 계속 업데이트 해주는 것이 핵심이라고 할 수 있는 알고리즘이다.
# 입력
n = int(input())
requests = list(map(int, input().split()))
budget = int(input())
print(f'실제 가진 예산은 {budget}입니다')
# 상한액이 upper_bound일 때 필요한 예산을 계산하는 함수
def calculate_needed_budget(upper_bound: int)->int:
needed_budget = 0
for request in requests:
needed_budget += min(request, upper_bound)
return needed_budget
# 상한액 최솟값을 low로, 상한액 최댓값을 high로 설정
low = 0
high = max(requests)
# 찾으려고 하는 적절한 상한액. 아직 정해지지 않았으므로 -1로 초기화
good_upper_bound = -1
while low <= high:
mid = (low + high)//2
if calculate_needed_budget(mid) <= budget:
good_upper_bound = mid
low = mid + 1
else:
high = mid - 1
answer = -1
for request in requests:
given = min(request, good_upper_bound)
answer = max(answer, given)
print(answer)requests = list(map(int, input().split()))
백준 사이트의 입력 형식 처리를 위한 효율적인 코드를 구글링하여 찾았다. 파이썬은 엔터를 치기 전의 input()값을 한번에 문자열로 받아들이기 때문에 input().split()을 통해 공백을 기준으로 나누어서 list로 만들어 준다. input().split()은 결과를 str로 내보내기 때문에 이를 int로 바꿔주는 과정이 필요한데 map(int, input().split())을 통해 만들어줄 수 있다. 마지막으로 map()의 결과값이 list가 아니기 때문에 list(map(int, input().split()))를 사용하여 list로 변형시켜 준다.
•알고리즘
대충 이런 느낌(Colin's BLOG에서 참고)
