[백준 1654] 랜선 자르기 [java]

---

이분 탐색 문제로 풀었다.

 

이 문제에서 두 가지 주의할 점이 있는데

 

하나는 범위가 커서 long형으로 선언해야하는 점과 문제에서 랜선의 길이는 자연수라는 점이다.

 

우선 랜선의 길이는 1부터 주어진 랜선들 중 가장 긴 랜선의 길이가 될 수 있다.

따라서 1과 가장 긴 랜선의 길이의 평균 값을 기준으로 위아래로 찾아보면 된다.

 

코드

package baekjoon;

import java.util.Scanner;

public class cut_lanwire {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        long n = scan.nextLong();
        long arr[] = new long[k];
        long max = 0;

        for(int i = 0;i<k;i++){
            arr[i] = scan.nextLong();
            max = Math.max(max,arr[i]);
        }

        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){ // sum이 더 많으면 자르는 길이를 늘릴 필요가 있음
                left = mid+1;
            }else{ // sum이 더 적으면  자르는 길이를 줄일 필요가 있음
                right = mid-1;
            }
        }
        System.out.println(right);
    }
}