이분 탐색 예제

https://www.acmicpc.net/problem/2512

 

찾고자 하는 값 : 최적의 상한액

탐색 범위 : [ 0, 지방 요청 금액 중 최댓값 ]

시뮬레이션 : [ 0, 150 ] -> [ 75, 150 ] -> ...

N = int(input())
jibang = list(map(int, input().split()))
budget = int(input())

left = 0
right = max(jibang)
answer = -1

while left <= right:
    middle = (left + right) // 2
    
    sum = 0
    for i in range(N):
        sum += min(middle, jibang[i])
        
    if sum <= budget:
        answer = middle
        left = middle + 1
    else:
        right = middle - 1
        
print(answer)

 

https://www.acmicpc.net/problem/2343

 

 

# 탐색하려는 값 : 블루레이의 용량
# 탐색 볌위 : [ 영상길이의 최댓값, 영상길이의 합 ]

N, M = map(int, input().split())
running_time = list(map(int, input().split()))

left = max(running_time)
right = sum(running_time)
answer = -1

print(left, right)

while left <= right:
    middle = (left+right)//2
    
    blueray_num = 1
    remain = middle
    
    for i in range(N):
        if remain < running_time[i]:
            blueray_num += 1
            remain = middle
        
        remain -= running_time[i]
        
    # 블루레이 몇 개 썼는지 확인
    if blueray_num <= M: # 만족시
        answer = middle # 답의 후보로 기록
        right = middle-1 # [left, middle-1]
    else:
        # 불만족시
        left = middle+1 # [middle+1, right]

print(answer)