[이코테] 이진 탐색 : 떡볶이 떡

문제

적어도 M만큼의 떡을 가져가기위해 설정할 수 있는 최대 높이를 구하는 문제

• 이진 탐색 문제

✍️ 나의 풀이

• 순차탐색은 말도 안되게 오래 걸린다.
• 따라서, 이진 탐색을 통해 M보다 적은 떡이면 높이를 낮춰 자르고 M보다 많은 떡이면 높이를 높혀 최대 높이를 구하도록 한다.

🛠 나의 코드

n, m = map(int, input().split())
height = list(map(int, input().split()))

height.sort(reverse=True)
end = height[0]
start = 0

mx = -1
while start <= end:
    inspection = (start + end) // 2
    sm = 0
    for h in height:
        if h > inspection:
            sm += (h - inspection)
    if sm >= m:
        start = inspection + 1
        mx = max(mx, inspection)
    elif sm < m:
        end = inspection - 1
print(mx)

📝 정리

• 이진 탐색 -> 새로운 start와 end 설정 시 +1, -1을 해줘야 한다. 또한 이진 탐색의 종료조건은 start <= end

🎈 참고

• 이것이 취업을 위한 코딩테스트다 with python