이진 탐색: 떡볶이 떡 만들기

떡을 자르기 위해 칼날의 높이를 설정해야 한다.

길이가 일정하지 않은 여러개의 떡이 있는데, 떡이 칼날 높이보다 높으면 잘린 만큼 떡을 가져갈 것이고

떡이 칼날 높이보다 낮으면 잘리지 않는다.

 

떡의개수n,필요한 떡의 총 길이m을 첫 줄에 입력받고

두번째 줄에서 떡의 개별 높이를 한 줄에 입력받는다.

 

m만큼의 떡을 얻기 위해 최대한으로 높일 수 있는 칼날의 높이를 구하라.

 

---

n,m=map(int,input().split()) #떡의개수n, 용청한 떡의길이m
h=list(map(int,input().split())) #개별떡의길이

 k=max(h)-1 #절단기 높이 초기값
 for kal in range(k,0,-1):
     sum=0
     for teok in h:
         if teok>kal:
             sum+=teok-kal
     if sum>=m:
         print(kal)
         break

#이렇게 풀면 시간초과가 날 수 있음

맨 처음 풀이

칼날의 초기높이를 가장 긴 떡의 길이만큼으로 설정해 두고

칼날을 1씩 낮추면서, 잘랐을 때 얻을 수 있는 떡의 양이 m 이상이면 break하는 반복문을 만들었다.

간단한 방법인데.. 이 방법을 쓰게되면 떡의 길이가 어마어마하게 긴 경우는 계산하려면 한세월이 걸린다

 

이진탐색을 이용하면 떡의 길이가 길어도 시간초과를 안 낼 수 있다.

def binary_search(start,end,target):
    mid=(end+start)//2
    if start>=end:
        return mid    
    sum=0
    for i in h:
        if i>mid:
            sum+=(i-mid)
    
    if sum==target:
        return mid
    elif sum<target: #합이 작을때: 칼날길이를 더 낮춰야함
        return binary_search(start,mid-1,target)
    elif sum>target: #합이 클 때: 칼날을 더 높여야함
        return binary_search(mid+1,end,target)
        
result=binary_search(0,max(h),m)
print(result)

재귀함수를 이용한 이진탐색 풀이

(시작,끝,필요한 떡의 총길이)를 받는다

시작점과 끝점 사이 중간값을 칼날 길이로 설정하고, 잘릴 떡의 길이를 계산한다

잘린 떡의 길이가 부족하다면 칼날을 더 낮추고 => end값을 mid-1로 변경하여 재귀함수를 반환

잘린 떡의 길이가 많으면 칼날을 더 높인다 => start값을 mid+1로 변경하여 재귀함수를 반환

 

나는 재귀함수를 반환하는 부분에서

return을 쓰는걸 빼먹어서 왜 안되나 한참 헤맸다

 

 

 

start=0
end=max(h)

result=0
while(start<=end):
    total=0
    mid = (start + end)//2
    for x in h:
        if x>mid:
            total += x-mid
    if total < m:
        end = mid-1
    else:
        result = mid
        start = mid +1

print(result)

이건 반복문을 이용한 이진탐색

내용은 동일하다