[백준] 1654 - 랜선 자르기

앞서 푼 이진탐색이랑 완전히 동일한 문제이다.

다만 start를 0으로 두면 이후에 divide by 0 예외가 뜨므로, 문제 조건대로 꼭 1로 설정을 해두자(자연수)

예외는 입력으로 K = 2, N = 2, 1, 1을 넣을 때 발생했다. start가 처음에 0이면, mid 값이 0이 되므로 에러가 발생한다. 유의하자.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        long[] lengths = new long[K];

        long max = 0;
        for(int i=0; i<K; i++) {
            lengths[i] = Long.parseLong(br.readLine());
            max = Math.max(max, lengths[i]);
        }

        long start = 1;
        long end = max;

        while(start <= end) {
            long mid = (start + end) / 2;
            int sum = 0;
            for(long x : lengths) {
                if(x >= mid) {
                    sum += x / mid;
                }
            }
            if(sum >= N) {
                start = mid + 1;
            } else
                end = mid - 1;
        }
        System.out.println(end);
    }
}