랜선 자르기
면접 대비시간 제한2초메모리 제한128 MB
K개의 케이블 길이가 주어질 때, 각 케이블에서 나오는 조각 수의 합이 N개 이상이 되도록 하는 최대 정수 절단 길이를 이분 탐색으로 구합니다.
문제
길이가 서로 다른 랜선 K개가 있다. 이 랜선들을 잘라서 모두 같은 길이인 랜선을 N개 이상 만들려고 한다.
랜선을 자를 때 길이 손실은 없으며, 이미 자른 랜선은 다시 이어 붙일 수 없다. 자르는 길이는 센티미터 단위의 양의 정수여야 한다. N개보다 많이 만드는 경우도 조건을 만족한 것으로 본다.
만들 수 있는 같은 길이 랜선의 최대 길이를 구하시오.
입력
첫째 줄에 이미 가지고 있는 랜선의 개수 K와 필요한 랜선의 개수 N이 주어진다.
1 <= K <= 10,0001 <= N <= 1,000,000K <= N
이후 K개의 줄에 각 랜선의 길이가 센티미터 단위의 자연수로 주어진다. 각 길이는 2^31 - 1 이하이다.
출력
N개 이상 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
힌트
길이를 200cm로 정하면 802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 얻어 총 11개를 만들 수 있다.