[이코테] 파라메트릭 서치

파라메트릭 서치 : 최적화 문제를 결정 문제(예 혹은 아니오)로 바꿔 해결하는 기법

ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

 

일반적으로 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용해 해결할 수 있음

 

# 떡볶이 떡 만들기

# 떡의 개수N 과 요청한 떡의 길이 m 입력
n,m = list(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 기록
        result = mid 
        start = mid + 1
print(result)