99클럽 코테 스터디 11일차 TIL + 이분탐색

https://www.acmicpc.net/problem/16401

# 16401 과자 나눠주기

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
snack = sorted(list(map(int, input().split())))

start = 1
end = snack[-1]

answer = 0
while start <= end:
    mid = (start + end) // 2

    cnt = 0 # 길이가 mid인 것을 만들 수 있는 개수
    for s in snack:
        cnt += s // mid
        
    if cnt >= m:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1
print(answer)

• 이분 탐색으로 조카에게 나눠줄 막대 과자의 최대 길이 (mid) 를 구해야 한다.
• 이분 탐색은 오름차순 정렬을 해야 한다.
• 최소 길이 1인 막대과자로 나눠야 하기 때문에 start = 1 , end = 입력 받은 막대과자의 최대길이 로 설정한다.
• 길이가 mid 인 것을 만들 수 있는 개수를 cnt라 할 때 조카 수보다 많다면 막대과자의 길이(mid)를 늘려야 한다.