[백준 / 실버2] 1654 랜선 자르기 (Java)

문제 보기

사용한 것

• 최대 랜선의 길이를 효율적으로 구하기 위한 이분 탐색

풀이 방법

• 입력 값으로 초기화, max에 가지고 있는 랜선 중 최대 길이를 저장한다.
• 이분 탐색을 사용하여 필요한 랜선의 개수보다 많이 자를 수 있는 최대 길이를 구한다.
• 오버헤드가 발생할 수 있으므로 long 자료형이 필요할 수 있다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int k = Integer.parseInt(line[0]);
        int n = Integer.parseInt(line[1]);
        int[] arr = new int[k];
        int max = 0;
        for (int i = 0; i < k; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        // 이분 탐색
        long l = 1;
        long r = max;
        while (l <= r) {
            long m = (l + r) / 2;
            long ct = 0;
            for (int i = 0; i < k; i++) {
                ct += arr[i] / m;
            }

            if (ct >= n) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        System.out.println(r);
    }
}