떡볶이 떡 만들기

떡볶이 떡 만들기

해결방법

이 문제는 이진탐색 문제이면서 파라메트릭 서치 유형의 문제이다.

파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법

‘원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제’

이진 탐색으로 잘라야 할 높이를 찾아가면 된다.

def make(dduck, mid): # 잘랐을 때 만들어지는 떡의 길이를 반환하는 함수
    result = 0
    for dd in dduck:
        if dd > mid:
            result += (dd - mid)
        else:
            continue
    return result

def check(target, dduck, start, end):
    while start <= end:
        mid = (start + end) // 2 # 절단기에 설정하는 높이
        res = make(dduck, mid)
        if target == res:
            return mid
        elif target < res:
            start = mid + 1
        else:
            end = mid - 1
    return False


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

dduck.sort()
result = check(m, dduck, 0, dduck[-1])
print(result)