Java) 1654번 랜선 자르기 (이진 탐색법)

이번 문제는 k개의 랜선에서 N개로 최대 길이를 만드는 문제입니다.

최대로 큰 값을 찾는 방법은 Math 라이브러리를 사용했어요.

max = Math.max(max,cable[i])는 max와 cable[i]와 값을

비교하며 더 큰 값을 max 넣는 방식입니다.

 

1. 먼저 K와 N값을 입력받습니다.

2. K 중에서 최대 길이의 랜선을 찾습니다.

3. 최대 케이블을 이진 탐색으로 값을 찾습니다.

4. 만약 total>=N이면 더 큰 값이 될 수도 있기 때문에 low의 값을 middle로 설정합니다.

5. total <=N이면 길이가 더 작아야 하기 때문에 high 값을 middle로 합니다.

6. low 값이 high보다 커지면 더 반복할 수 없으니 반복을 빠져나옵니다.

 

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[] cable = new long[K];
        long max = 0;
        
        for (int i=0; i<K; i++) {
            cable[i] = sc.nextLong();
            max=Math.max(max,cable[i]);
        }

         long high=max;
         long low=1;
         while(low<=high){
             long middle=(high+low)/2;
             long total=0;
             for(int j=0;j<K;j++){
                 total+=cable[j]/middle;
             }
             
             if(total>=N){
                 low=middle+1;
             }else{
                 high=middle-1;
             }
         }
         
         System.out.println(high);

         sc.close();
    }
}