TIL::0721_이분 탐색/boj_2512번

백준 2512번: https://www.acmicpc.net/problem/2512

2512번: 예산

 

--

 

import sys

n = int(sys.stdin.readline())
budget = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())

_max = max(budget) 
_min = 1 


while _max >= _min:
    mid = (_max + _min) // 2 
    res = 0 

    for i in budget:
        
        if mid < i:
            res += mid
        else:
            res += i

    if res > m:
        _max = mid - 1
    else:
        _min = mid + 1

print(_max)

 

이분 탐색 (Binary Search) : 찾고자 하는 수를 두 부분으로 나누어서 찾는 기법으로

                                            순차 탐색(linear search)보다 더 빠름!

 

이분 탐색의 탐색 순서:

1. 탐색 리스트가 정렬이 되어 있지 않다면 정렬
2. left, right, mid를 잡아줌 (리스트 첫 번째는 left, 리스트 마지막은 right, 리스트의 중간 값은 mid
   1. 여기서 값보단 리스트의 인덱스로 잡는 것이 더 범용적으로 사용할 수 있음
3. mid 값과 찾고자 하는 값 비교
4. mid값이 더 크면 right 값을 mid -1, mid값이 더 작으면 left값을 mid + 1로 세팅
5. left > right가 될 때까지 2~4번 반복