[백준] 랜선 자르기 1654번 - Java

[백준] 랜선 자르기 1654번

나의 풀이

public class CuntLanCable {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] values = br.readLine().split(" ");
        int K = Integer.parseInt(values[0]);
        int N = Integer.parseInt(values[1]);
        int[] cables = new int[K];
        for(int i = 0; i < K; i++) {
            cables[i] = Integer.parseInt(br.readLine());
        }
        long start = 1;
        long end = Arrays.stream(cables).max().getAsInt();

        while(start <= end) {
            long count = 0;
            long mid = (start + end) / 2;
            for(int cable : cables) {
                count += cable / mid;
            }
            if(count >= N) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        System.out.println(end);
    }
}

• 입력받은 숫자들 중에서 가장 큰 숫자를 끝으로 잡고 이분 탐색을 돌린다.
• 중간 값으로 잘랐을 경우 랜선의 개수를 계산해준다.
• 랜선의 개수가 K 보다 많거나 같다면 start 를 mid + 1 해준다. 같다면 조건을 넣어줘야 최대값을 구할 수 있다.
• 랜선의 개수가 K 보다 적다면 end 를 mid - 1 해준다.
• 랜선의 개수가 많다는 것은 랜선의 길이를 짧게 잡았다는 뜻이고, 랜선의 개수가 적다는 것은 랜선의 길이를 길게 잡았다는 의미이다.
• 그렇게 해서 start 가 end 보다 커지면 반복이 종료되는데 이 때 end 가 만족하는 값 중 최대값이 된다.