[JAVA]백준_1654_랜선자르기

문제링크

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

1654번: 랜선 자르기

 

기본적인 이분탐색 문제이다.

이분탐색 이해가 잘 안되어서 풀어보았다.

중간에 많이 틀렸는데 

left,right,mid 를 long형으로 해주어야 한다.

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_1654{
    static  int K,N;
    static int arr[];
    static int result = 1;// 랜선의 최대 길이 저장
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken()); //가지고 있는 랜선의 개수
        N = Integer.parseInt(st.nextToken()); //필요한 랜선의 개수
        arr = new int[K];


        for(int i=0;i<K;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        long left = 1;
        long right = arr[K-1];
        while (left<=right){
            int cnt = 0;
            long mid = (left+right)/2;

            for(int i=0;i<K;i++){
                cnt += arr[i]/mid;
            }

            if(cnt >= N){
                result = (int) Math.max(mid,result);
                left = mid+1;
            }
            else{
                right = mid-1;
            }
        }

        System.out.println(result);
    }
}