[JAVA] 백준 1654 랜선자르기_이분탐색

 

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

 

 

접근 : 

 

 - 랜선을 특정한 이분 탐색을 통하여 자른다.

 

 - 만약 자른 갯수가 목표치 이상이면, left = mid + 1 보다 작으면 right = mid - 1 로 끝까지 진행한다. 

 

 - 탐색이 완료되는 곳을 정답으로 출력한다.

 

 

 

코드구현 : 

 

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

public class Main {

    private static boolean calFunc(int[] nums, long mid, int target ){
        long temp_res = 0;
        for(int num : nums){
            temp_res += num / mid; 

            if(temp_res >= target) return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");        
        int k = Integer.parseInt(temp[0]);
        int n = Integer.parseInt(temp[1]);

        int[] nums = new int[k];

        for(int i = 0; i < k ; i++) nums[i] = Integer.parseInt(br.readLine());

        long left = 1;
        long right = Integer.MAX_VALUE;
        long mid = 0;
        long answer = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if(calFunc(nums, mid, n)){
                answer = mid;
                left = mid + 1;
                continue;
            }
            right = mid - 1;
        }

        System.out.println(answer);
        br.close();
    }
}