[백준2512&파이썬] 이분탐색은 YES or NO인지 묻는 것이다.

# 문제

백준 2512 예산 파이썬 풀이

2512번: 예산

# 코드

import sys

N = int(sys.stdin.readline()) # 지방의 수
cites = list(map(int,sys.stdin.readline().split()))
MAX = int(sys.stdin.readline()) # 최대 예산

left = 1
right = max(cites) # MAX 잡았었는데 틀렸음. 예산이 도시에 들어가는 것보다 작을 수 있음

result = -1
while left <= right :
  mid = (left + right) // 2

  used_money = 0
  for city in cites :
    if mid <= city :
      used_money += mid
    else :
      used_money += city

  if MAX < used_money : # 돈을 더 많이 쓴 경우
    right = mid - 1
  else :
    # MAX > used_money
    left = mid + 1
    result = mid

print(result)

# 풀이

• 이분탐색을 이용해서 풀 수 있다. 이분탐색을 풀이에 적용할때는 이분탐색을 진행하면서 나오는 mid값이 후보가 되어, mid를 사용해서 문제의 조건을 계산했을때 이것을 만족하나 안하나 (YES / NO )의 여부로 생각하면 쉽다.
• 위 문제에서도 이분탐색으로 뽑은 mid가 예산의 후보가 된다. 해당 값으로 계산 했을때 예산을 초과한다면 예산을 늘려주고, 예산을 초과하지 않는다면 예산을 줄여줘서 최적의 값을 찾아가는 형식이다.
• 이분탐색은 상상외로 빠르다. log N 이기 때문에 10억의 값이 있더라도 30번이면 정답을 찾을 수 있다.