백준 랜선자르기

랜선 자르기

길이가 제각각인 K개의 랜선을 같은 길이로 잘라, 길이가 가장 긴 N개 를 만드는 문제이다.
문제를 읽고도 풀이가 떠오르지 않아 한동안 헤맸다. 이진 탐색 문제라는 것을 알면서도 쉽게 아이디어가 떠오르지 않았는데,
배열에서 특정 값이 존재하는지 찾는 기본적인 이진 탐색 활용만 이해하고 있었기 때문인 것 같고, 하한·상한 의 개념이 정확히 잡히지 않아 어려웠던 것 같다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        long[] arr = new long[k];
        for (int i = 0; i < k; i++) {
            arr[i] = sc.nextLong();
        }
        Arrays.sort(arr);
        long start = 1;
        long end = arr[k - 1] + 1;

        while (start < end) {
            long mid = (start + end) / 2;
            long total = 0;
            for (int i = 0; i < k; i++) {
                total += arr[i] / mid;
            }
            if (total < n) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        System.out.println(end - 1);
    }
}

어떤 길이로 랜선을 자를 때 잘린 랜선의 개수가 N보다 부족해지기 직전(상한)을 찾아, 그 값에서 1을 빼면 되는 문제였다.