[이진탐색] 고정점 찾기

문제

이것이 코딩테스트다 201p

풀이접근

파라메트릭 서치 유형의 문제로, 해결에 이진 탐색을 활용할 수 있습니다. 파라메트릭 서치는 최적화 문제를 결정 문제로 전환하여 해결하는 기법입니다. 결정 문제는 '예' 또는 '아니오'로 답하는 문제를 의미합니다. 주로 파라메트릭 서치는 '주어진 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 사용됩니다. 예를 들어, 특정 범위 내에서 조건을 만족하는 가장 큰 값을 찾는 최적화 문제라면, 이진 탐색을 통해 결정 문제를 해결하면서 범위를 축소할 수 있습니다. 따라서 이 문제에서는 '현재 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 후, 조건의 만족 여부에 따라 탐색 범위를 축소하여 해결할 수 있습니다. 범위 축소에는 이진 탐색의 원리를 활용하여 절반씩 탐색 범위를 줄여가게 됩니다.

풀이

N, M = map(int, input().split())
lens =list(map(int, input().split()))

target = 0
start, end = 0, max(lens)

while (start <= end) : # 탈출 조건 잘 생각하자
  remains = sum([(x - target) for x in lens])
  mid = (start+end)//2
  if remains < M : # 잘린 떡이 주문보다 적을때 (조금 더 많이 자르기)
    end = mid-1
  else : # 잘린 떡이 주문보다 크거나 같을때
    start = mid+1
    result = remains # 일단 기록

print(result)