[BOJ] 백준 [1654] 랜선 자르기 JAVA

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제

 

풀이

전형적인 이분탐색 문제이다. right left를 정해놓고 진행할때마다 점점 중간값으로 탐색하는 방식으로 하면된다.

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int K,N;
    static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        K = Integer.parseInt(input[0]); N = Integer.parseInt(input[1]);
        long max=0;
        arr = new long[K];
        for(int i=0;i<K;i++) {
            arr[i] = Long.parseLong(br.readLine());
            max = Math.max(arr[i],max);
        }
        long left = 1;
        long right = max;
 
        while(left<=right){
            long mid = (right+left)/2;
            long sum = 0;
            for(int i=0;i<K;i++){
                sum += arr[i]/mid;
            }
            if(sum >= N)
                left = mid+1;
            else
                right = mid-1;
        }
        System.out.println(right);
 
    }
}