이진탐색

2부 - 2번 부품찾기 p.197

def Bis(arr, N, key):
    arr.sort()
    start,end = 0,N-1

    while start <= end:
        middle = (start+end)//2
        if key == arr[middle]:
            return True
        elif key < arr[middle]:
            end = middle - 1
        elif key > arr[middle]:
            start = middle + 1
    return False
    
N = int(input())
have = list(map(int, input().split()))
M = int(input())
buy = list(map(int, input().split()))

for i in buy:
    if Bis(have, N, i):
        print("yes", end=" ")
    else:
        print("no", end=" ")

---

2부 - 3번 떡볶이 떡 만들기 p.201

N, M = map(int, input().split()) # 떡의 개수/ 떡의 길이
H = list(map(int, input().split())) # 떡의 높이들

result = max(H)
H.sort()

while True:
    sum_cake = 0
    for cake in H:
        if cake > result:
            sum_cake += cake - result
    
    if sum_cake == M:
        break
    
    result -= 1

print(result)

이진탐색 이용

N, M = map(int, input().split()) # 떡의 개수/ 떡의 길이
H = list(map(int, input().split())) # 떡의 높이들

start = 0
end = max(H)
result = 0

while start <= end: # start = end 될 때까지 돌리기
    total = 0
    mid = (start+end)//2
    for i in H:
        if i > mid:
            total += i - mid
    if total < M:  # 떡의 양이 부족한 경우
        end = mid - 1
    else:   # 떡의 양이 충분한 경우
        result = mid
        start = mid + 1

print(result)

max값부터 탐색하는 아이디어는 맞았다...!