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

1. 문제 설명

- 주어진 떡의 길이들을 자르고 남은 것들을 손님이 가져가게 되는데, 손님이 가져갈 수 있는 떡볶이 양을 정확하게 맞출 수 있게 높이를 구하는 문제

- 떡을 최대한 덜 자르면서 손님에게 줄 수 있게 하는 것이 문제의 포인트다.

2. 코드

# 입력
n, m = list(map(int, input().split()))
array = list(map(int, input().split()))
"""
3, 6
19 15 10 17
"""
# 변수 초기화
start= 0
end = max(array) # 19
result=0

# 높이 계산
while(start < end):
    mid = (start+end)//2
    tmp = list(map(lambda x: x-mid if x > mid else 0, array)) # 떡의 양을 계산
    if sum(tmp) > m:
        start = mid+1
    elif sum(tmp) < m:
        end = mid -1
    else: # 최대한 덜 잘랐을 때가 정답이므로, else에 해당 조건이 들어가야 한다.
        result = mid
        break
        
print(result)

"""
>> 15
15로 잘랐을 때 19-15=4, 17-15=2 로 4+2=6이 된다.
"""

3. 코멘트

- 탐색해야 하는 범위가 10억까지 크기 때문에 이진탐색을 고려해야 한다.

- 종종 코딩 문제 풀 때 잘 풀었다고 생각해도 시간이 오래 걸리는 경우는 순차탐색을 했기 때문이다. 문제의 범위가 너무 길다면 무조건 이진탐색을 생각하도록 하자.