[백준] 온라인 저지 1654번 : 랜선 자르기(Java), 이분 탐색

이분 탐색으로 풀이

> 문제의 핵심은 N개의 랜선을 만드는 데 사용될 수 있는 최대 길이를 찾는 것

> 이분 탐색은 최솟값이나 최댓값을 구하는 문제에서 많이 활용됨

> mid 값을 기준으로 해당 길이가 가능한지 체크하며 탐색 범위를 좁히는 방식

 

 

* int형 선언이 아닌 long으로 선언할 것 주의

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

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

		int K = Integer.parseInt(st.nextToken()); // 랜선 수
		int N = Integer.parseInt(st.nextToken()); // 필요한 랜선 수
		int[] 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[arr.length - 1];

		while(left <= right) {
			long mid = (left+right) / 2;
            		long count = 0;
            
			for(int i=0; i<arr.length; i++) {
				count += arr[i] / mid;
			}

			if (count >= N) {
                            left = mid + 1; 
                        } else {
                            right = mid - 1; 
                        }
		}
		System.out.println(right);
	}
}