15. 이진 탐색: 떡볶이 떡 만들기

input:

4 6 <--- 떡의 개수와 얻어야 하는 떡 길이 (N, M)

18 29 21 13 <--- 떡

rule:

높이를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이보다 긴 떡은 잘리고, 낮은 떡은 잘리지 않는다.

적어도 M만큼의 떡을 가질 수 있는 절단기의 높이의 최댓값 구하라.

 

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

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

start = 0
end = max(dduck)
result = 0

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

전형적인 이진 탐색 문제, 파라메트릭 서치 유형.

파라메트릭 서치는 최적화 문제를 예, 아니오로 바꾸어 해결하는 것이다. (이진 탐색)

보통 파라메트릭 서치는 이진 탐색을 이용하여 해결한다.

자른 떡을 합친 값을 기준으로 이진 분류를 하는 점이 인상적이다.

그리고 배열에서 특정 값이나 찾는 줄 알았던 이진 탐색이 현실 문제에서도 적용되는 것이 굉장히 인상적이다.