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

<이것이 취업을 위한 코딩 테스트다>를 공부하며 정리한 내용입니다.

문제

떡의 개수 N과 요청한 떡의 길이 M, N개의 떡 개별 높이가 주어졌을 때, 손님이 적어도 M만큼 가져갈 수 있도록 절단기 최대 높이를 결정하는 문제다.

예를 들어 높이가

19, 14, 10, 17cm인 떡이 나란히 있고, 절단기 높이를 15cm로 지정하고 자르면

15, 14, 10, 15cm가 된다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이고, 절단기 높이보다 아래면 잘리지 않는다.

입력 조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1≤N≤1,000,000, 1≤M≤2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

입력 예시

4 6

19 15 10 17

출력 예시

15

---

해설

내 풀이

• 절단기 최소 높이 start (0) ~ 최대 높이 end (=떡 개별 높이 최댓값) 를 가지고 이진 탐색하기
  → 반으로 범위 줄이기🍀
  
• 떡 자른 결과가 목표치보다 작으면 현재 절단기 높이를 저장(best)하고, 최댓값이 나타나면 값을 갱신해준다.
• 떡 자른 결과를 계산해주는 함수를 따로 구현
• 떡 높이 리스트를 미리 정렬하였음. 그래서 결과를 보다 빠르게 계산할 수 있도록! 작은 값 나타나면 더이상 계산 ❌

#떡볶이 떡 만들기

#절단기 최소 높이~ 최대 높이를 가지고 이진 탐색!!

#떡 자른 결과 계산기
def height_calculator(hlist, cut):
    res=hlist[0]-cut
    for i in range(1,len(hlist)):
        if cut>=hlist[i]:
            break
        res+=(hlist[i]-cut)

    return res
    

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

h.sort(reverse=True) #내림차순 정렬

#최적 높이 이진 탐색

start=0 #최소 높이 
end=h[0] #최대 높이=최대 떡의 높이
best=0 #절단기 최대 높이

while start<=end:
    mid=(start+end)//2

    hmid=height_calculator(h, mid) #mid로 자른 결과

    if hmid<m: #목표치보다 작으면 
        end=mid-1 #절단기 길이를 더 짧게

    elif hmid==m: #목표치와 같으면 
        best=mid #니가 답.
        break

    else: #목표치보다 크면
        if best<mid: #현재 최적 높이보다 크다면
            best=mid #니가 최적 높이
            
        start=mid+1 #절단기 길이는 더 늘리기
        

print(best) #최적의 해 출력