[Python] 이코테 떡볶이 떡 만들기 (Binary Search)

📌 문제

---

📌 풀이

👆 첫 번째 시도 (선형탐색→시간초과)

• 이진탐색 파트인 건 알지만 왜 이진탐색을 써야 하는지 몰랐음
• 절단기의 높이를 가장 긴 떡의 길이로 설정하고 1씩 줄여나가면서 잘린 떡의 길이(rest)의 합을 계산

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

for i in range(height[0], 0, -1):
    rest = list(map(lambda x: x-i if x>i else 0, height))
    if sum(rest)>=m:
        print(i)
        break

✌ 두 번째 시도 (이진탐색)

• 떡의 길이와 절단기의 높이는 0부터 10억까지의 정수 중 하나이다.
• 이렇게 큰 탐색 범위를 보면 단순히 선형탐색을 사용하였을 때 시간초과 판정을 받을 수 있으므로 이진탐색을 떠올려야 한다.

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

low = 0
high = max(height)
answer = 0

while (low <= high):
    mid = (low + high) // 2
    rest = list(map(lambda x: x-mid if x>mid else 0, height))
    if sum(rest)<m:
        high = mid - 1
    else:
        answer = mid
        low = mid + 1

print(answer)