테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 과자 나눠주기 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:binsearch#maximum_valid_integer|teflib.binsearch.maximum_valid_integer]]

{{tag>BOJ ps:problems:boj:실버_3}}