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

이진탐색 + 파라메트세트릭 서치

로직

1. nm 입력받기 (n:떡개수, m:요청길이)

2. dduk (list) 입력받기

3. dduk 정렬하기

4. while(true) :
   중앙값을 잡아준다
   mid=(start+end)//2
   절단할 기준을 중앙값으로 잡아준다
   n = dduk[mid]

   떡을 하나씩 기준n대로 잘라주고 total에 고객이 가져갈 값을 넣어준다
   for i range(len[dduk]):
   result = dduk[i]-n
   total += result

   if total == m:
   return n
   elif total > m :
   start = mid+1
   elif total < m :
   end = mid-1
   '

코드

import sys
n,m = map(int,input().split())
dduk = list(map(int,sys.stdin.readline().split()))
dduk.sort()

start=0
end=max(dduk)

result=0
while start <= end :
  print('start', start)
  print('end',end)
  mid = (start+end) // 2
  print('mid', mid)

  total=0
  #떡의 개수만큼 반복
  for i in range(len(dduk)):
    # 떡길이-기준(n) 
    if dduk[i] > mid :
     total += dduk[i]-mid
      # 고객이 가져가는 총 길이 toal

  # 가져가는 양 < 요청길이 (n이 작아져야함 - 왼쪽부분탐색)
  if total < m :
    end = mid-1
  # 가져가는양 > 요청길이 (n이 커져야함 - 오른쪽부분 탐색)
  else :
    #최대한 덜 잘렸을 때가 기준이므로 여기서 기록!!
    result= mid
    start = mid+1

print(result)

주의사항

• mid : 중앙값은 떡 길이의 중앙값이다
  -> 인덱스의 중앙값이 아니다 !!
• 떡 길이가 > mid 일 경우에만, 떡을 자른다
• 생각을 잘 해야한다..
  1) 가져가는 길이 < 요청길이 : 왼쪽부분을 탐색
  -> end = mid-1
  2) 가져가는 길이 > 요청길이 : 오른쪽 부분 탐색
  -> start= mid+1
• 떡의 길이가 조금 남더라도 최대한 덜 잘렸을 때가 기준이므로 else 부분에서 결과값을 기록해두어야 한다