[BOJ/Python] 백준 2512번 - 예산

백준 #2512 예산

2512번: 예산

import sys
input = sys.stdin.readline

n = int(input())   # 지방의 수
reqs = list((map(int, input().split())))   # 각 지방의 예산 요청
m = int(input())   # 총 예산

left = 0
right = max(reqs)

while left <= right:
  mid = (left + right) // 2   # 상한액
  req_sum = 0
  for req in reqs:
    if req > mid:   # 요청액이 상한액보다 클 경우 상한액으로 계산
      req_sum += mid
    else:   # 요청액이 상한액보다 작을 경우 요청액으로 계산
      req_sum += req
  if req_sum > m:   # 요청액 합이 총 예산보다 클 경우
    right = mid - 1
  else:
    left = mid + 1
print(right)

이분 탐색 방법을 활용한다!

1. left와 right는 요청 가능한 금액의 범위를 의미한다. left의 초깃값은 0, right의 초깃값은 요청액의 최댓값으로 한다.
2. 상한액(mid)은 left와 right의 중간값으로 한다.
3. 요청액이 상한액보다 클 경우 상한액으로, 작을 경우 요청액으로 하여 각 요청들에 대한 전체 합을 구한다.
4. 전체 합이 총 예산보다 클 경우 right를 중간값 - 1로, 작을 경우 left를 중간값 + 1로 한다. (값이 크면 값을 줄여야 하니까 범위의 최댓값인 right 값을 줄이고, 값이 작으면 값이 커져야 하니까 범위의 최솟값인 left 값을 높이는 것!)
5. 탐색을 반복하다 left 값이 right 값보다 커졌을 때 반복을 중단한다.
6. 범위의 최댓값인 right 값이 예산들 중 최댓값이 된다.