[Python] 이코테 - 떡볶이 떡 만들기 (이진탐색)

문제

 

---

👆 첫 번째 시도 (선형탐색)

- 이진탐색 파트인 건 알지만 왜 이진탐색을 써야 하는지 몰랐음

- 절단기의 높이를 가장 긴 떡의 길이로 설정하고 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)