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

문제

Baekjoon 16401: 과자 나눠주기

• 설명: 과자들의 크기가 주어졌을 때 M개를 넘도록 과자를 자를 수 있는 최대 길이를 구하여라

풀이

• 과자를 1로 자르면 거의 대부분의 테스트 케이스에서 가능하다
• 이렇게 숫자를 늘려나가다보면 언젠가 부터 모든 학생들에게 나눠줄 수 없어지는 첫 길이가 생기게 된다.
• 우리는 이 경계를 찾으면 되는데 숫자의 범위가 굉장히 크고, 범위가 이분법적으로 나누어져있기 때문에 이진탐색을 사용하여 찾아준다.

오늘의 회고

• 오랜만에 풀어보는 이진탐색이지만 확실히 개념을 익혀두니 쉽게 잊어먹지 않는 것 같다.

Code

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

def get_num(size):
    result = 0
    for s in snack:
        result += s // size

    return result

left, right = 0, 1_000_000_000
while left + 1 < right:
    mid = (left + right) // 2

    if get_num(mid) >= m:
        left = mid
    else:
        right = mid

print(left)