[백준] 2512 - 예산 / Python / 실버 3

🚩문제 주소

📄풀이

이분 탐색

최소 금액과 최대 금액을 반으로 나누어서 상한액으로 설정합니다.

모든 예산을 순회하여 각 예산이 상한액보다 작거나 같으면 예산을 더해주고, 크다면 상한액을 더해줍니다.

전부 더한 값이 총 예산액보다 크다면 최대 금액을 상한액에서 1을 빼준 값으로 변경하고, 작거나 같다면 최소 금액을 상한액에서 1을 더해준 값으로 변경합니다.

이 과정을 계속 반복하다가 최소 금액이 최대 금액보다 커지면 반복을 종료하고 최대 금액을 출력합니다.

👨‍💻코드

N = int(input())
budgets = list(map(int, input().split()))
M = int(input())
start, end = 0, max(budgets) # 최소 금액, 최대 금액

while start <= end:
  mid = (start+end) // 2 # 상한액
  total = 0
  for budget in budgets:
    if budget <= mid: # 요구 예산액이 상한액보다 작거나 같으면
      total += budget # 예산액 더하기
    else:
      total += mid # 크다면 상한액 더하기
      
  if total > M: # 전부 더한 값이 총 예산액보다 크다면 최대 금액을 상한액 -1으로 변경
    end = mid - 1
  else: # 작거나 같다면 최소 금액을 상한액 +1로 변경
    start = mid + 1

print(end)