[Baekjoon Online Judge] 1654번: 랜선 자르기

1654번: 랜선 자르기

요구사항

 - 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

 - 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 

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

입력

 - 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

 - 첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

---

이분탐색을 진행하여 랜선을 자르고 개수를 늘려간다. 필요한 랜선의 개수가 n개 보다 크거나 같을 때 까지 이분탐색하며 적절한 랜선길이를 찾아간다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Baekjoon1654 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bufferedReader.readLine().split(" ");
        int k = Integer.parseInt(input[0]); // 랜선의 개수
        int n = Integer.parseInt(input[1]); // 필요한 랜선의 개수
        int[] wires = new int[k];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < k; i++) {
            wires[i] = Integer.parseInt(bufferedReader.readLine());
            max = Math.max(max, wires[i]);
        }

        Arrays.sort(wires); // 오름차순 정렬

        long start = 1;
        long end = max;

        while (start <= end) {

            long mid = (start + end) / 2;
            int count = 0;

            for (int wire : wires)
                count += wire / mid;

            if (count >= n) start = mid + 1;
            else end = mid - 1;
        }

        System.out.println(end);
        bufferedReader.close();
    }
}