과자 나눠주기

• 기본적인 이진 탐색 문제
• 나눠줄 조각의 길이를 l이라고 하면, 만들어질수 있는 l짜리 조각의 갯수가 M이상이 되는 최대의 l을 구하면 된다.
• 주어진 l에 대해서 조각의 갯수를 구하는 것은 O(N). 이진탐색의 범위는 1~max(L)이므로, 총 시간 복잡도는 O(N*log(max(L)))이 된다

"""Solution code for "BOJ 16401. 과자 나눠주기".

- Problem link: https://www.acmicpc.net/problem/16401
- Solution link: http://www.teferi.net/ps/problems/boj/16401

Tags: [Parametric search]
"""

from teflib import binsearch


def main():
    M, N = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    L = [int(x) for x in input().split()]

    try:
        answer = binsearch.maximum_valid_integer(
            1,
            max(L) + 1, lambda l: sum(x // l for x in L) >= M)
    except ValueError:
        answer = 0
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.binsearch.maximum_valid_integer