떡볶이 떡 만들기 [이진 탐색]

# 떡볶이 떡 만들기
# 10억 이상의 자료구조를 가진 연산이면 binary search 사용


   

n,m=map(int,input().split())
array=list(map(int,input().split())) # 떡 입력
start=0
end=max(array)

# 이진탐색 사용
while start<=end:
    print(start,end)
    total=0
    mid=(start+end)//2
    
    # 떡 탐색하면서 자르기
    for x in array:
        if x>mid:
            total+=(x-mid) # total은 잘린 떡의 총 길이
            
    if total<m: # 떡의 양이 목표 높이보다 작은 경우
        end=mid-1 # 더 많이 자르기 (왼쪽 부분 탐색)

    elif total>=m: # 떡의 양이 목표 높이보다 큰 경우
        start=mid+1 # 덜 자르기 (오른쪽 부분 탐색)
        result=mid # 최대한 덜 자를 때가 답 -> result 기록


print(result)

• 적절한 높이 h를 찾을 때까지 mid 값을 조정
• 이중 탐색에서 찾는 target을 범위에 맞게 조정한 후에 탐색하면 된다.
• 탐색 범위가 (1~10억) -> 이진 탐색
• 못 풀어서 답지 보고 풂