🔥

문제
집에서 시간을 보내던 윌리는 멘토님의 부름을 받고 급히 달려왔다. 멘토님은 캠프 때 쓸 N개의 케이블을 만들어야 하는데 너무 바빠서 윌리에게 도움을 청했다.


이미 윌리는 자체적으로 N개의 케이블을 가지고 있다. 그러나 N개의 케이블은 길이가 제각각이다. 멘토님은 케이블을 모두 M개의 같은 길이의 케이블으로 만들고 싶었기 때문에 N개의 케이블을 잘라서 만들어야 한다. 예를 들어 200cm 짜리 케이블에서 80cm 짜리 케이블을 두 개 잘라내면 40cm는 버려야 한다. (이미 자른 케이블은 붙일 수 없다.)


편의를 위해 케이블을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 N개의 케이블로 M개의 케이블을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. M개보다 많이 만드는 것도 M개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 케이블의 길이를 구하는 프로그램을 작성하시오.


입력
첫째 줄에 윌리가 이미 갖고있는 케이블의 개수 N과 멘토님이 필요한 케이블의 개수 M이 주어진다. (1 ≤ N ≤ 10,000,1 ≤ M ≤ 1,000,000)


그리고 항상 N ≤ M이다.


그후 N개의 줄에 걸쳐 윌리가 이미 갖고있는 케이블의 길이가 주어진다. 케이블의 길이는 2 ^31−1 보다 작거나 같은 자연수이다.


출력
첫째 줄에 M개의 케이블을 만들 수 있는 케이블의 최대길이를 출력한다.


예제 1 입력

4 11
802
743
457
539


예제 1 출력

200

예제 2 입력

2 13
157
877


예제 2 출력

78


Source

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class main{
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] cables = new int[n];
        for (int i = 0; i < n; i++) {
            cables[i] = sc.nextInt();
        }

        Arrays.sort(cables);

		int left = 1;
        int right = cables[n - 1];

        int maxLength = 0;
        while (left <= right) {
            int mid = (left + right) / 2;

            int count = 0;
            for (int i = 0; i < n; i++) {
                count += cables[i] / mid;
            }

            if (count >= m) {
                maxLength = mid;
                left = mid + 1;
            }
			else {
                right = mid - 1;
            }
        }

        System.out.println(maxLength);
	}
}

참고