[Ch.7 - 이진 탐색] 떡볶이 떡 만들기

 

My code

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

start = 0
end = max(array)

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

print(result)

Code Review

이번 문제는 손님이 요청한 떡의 길이가 m 일 때 적어도 m 만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제였습니다. 이 문제는 이진 탐색 알고리즘을 이용하여 해결할 수 있습니다. 먼저 시작 값을 0, 마지막 값을 입력 받은 길이의 최대값으로 설정한 후 mid 값을 설정해줍니다. 만약 입력 받은 떡의 길이가 mid 의 값보다 크다면 빼기를 해주어 total 값을 계산하여 저장해줍니다. 그런 다음 만약 계산한 total 값이 m 의 값보다 작다면 end 를 조정해주고, 그렇지 않다면 start 를 조정해줍니다. 이렇게 하면 이진 탐색처럼 절반만 탐색할 수 있게 됩니다. 또한 total 이 m 보다 클 때에만 mid 가 result 가 될 수 있으므로 이를 추가해줍니다. result 를 최종적으로 출력해주면 절단기에 설정할 수 있는 높이의 최댓값을 출력할 수 있습니다.