백준 > 2805 나무 자르기

 

매개변수 탐색을 이용해서 푸는 문제이다

이분 탐색이랑 비슷한듯 미묘하게 다른 느낌이다. 코드도 이분 탐색의 코드랑 비슷한 것 같다

 

최적화 문제를 결정 문제로 푸는 방법이라고 한다.

💡최적화 문제 : 어떤 알고리즘의 최적의 솔루션을 찾는 법

💡결정 문제 : 답이 이미 결정되어 있다고 보고 문제를 푸는 법

 

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

arr.sort()

def parametric(arr, m):
    start = 0
    end = arr[-1]
    
    while end >= start: #조건 수정
        mid = (start + end) // 2
        sum = 0
        
        for i in range(len(arr)):
            if arr[i] > mid:
                sum += arr[i] - mid
        if sum > m:
            start = mid + 1
        elif sum == m:
            return mid
        else:
            end = mid - 1
    return end
    
print(parametric(arr, m))