이진탐색 - 예제) 떡볶이 떡 만들기

💬 문제 이해

핵심) 절단기에 설정할 수 있는 높이의 최댓값을 구하시오
적어도 합쳐서 M만큼의 썰린 떡을 얻어야한다.

• 첫줄에 떡의 갯수 N과 요청한 떡의 길이 M이 주어진다
  (1<=N<=1,000,000 1<=M<=2,000,000,000)
• 둘째줄에 떡의 개별높이가 주어진다. (0<=높이<=10억)

발그림 ㅈㅅ 어차피 내가 이해하려고 그린거임

전형적인 이진탐색 문제이다 뭐??

🔍 Parametric Search

최적화 문제를 결정문제(yes or no)로 바꾸어 해결하는 기법
'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제' 에 주로 사용

ex) 범위 내에서 조건을 만족하는가장 큰 값 찾는 최적화 문제 등
➡️ 이진탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.

코테에서 보통 parametric search는 이진탐색을 이용하여 해결

💡 문제 풀이 아이디어

"적절한 높이를 찾을때까지 절단기 높이 H를 반복해서 조정하는 것"

절단기의 높이는 1부터 10억까지인데
이렇게 노답으로 큰 수를 보면 가장먼저 이진탐색을 떠올려야한다.

시간복잡도 검증
높이H 찾기 : 대략 31번
떡의갯수 N이 최대 100만개이므로 바꿀때마다 모든 떡 체크 : 31*100만 =대략 최대 3,000만번 연산

문제 시간제한은 2초이므로, 아슬아슬하게 시간초과 받지 않고 정답!

코드

# 떡의갯수 n, 요청한 떡의 길이 m
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별높이 정보 array 
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 = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
    start = mid + 1

print(result)