[BOJ] 1654번 랜선 자르기 - JAVA(자바)

💡 이분탐색(Binary Search) 문제

 

✅ 구하고자 하는 것 : N개를 만들 수 있는 랜선 최대 길이

• lt = 1
• rt = 랜선 길이 중 가장 긴 값  ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다.

자를 랜선의 길이가 mid이면 답으로써 가능한 숫자인가 검증 ➜ 얻을 수 있는 랜선의 개수를 구하는 함수 생성

• 얻을 수 있는 랜선의 개수가 N개 보다 크거나 같으면 자를 랜선의 길이를 늘려도 됨 lt=mid+1
• 반대면 랜선의 길이 줄이기 rt=mid-1

👨🏻‍💻 실행코드

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static int n, k;
    private static int[] arr;

    public static long count(long len) {
        long sum = 0;
        for(int i : arr) {
            sum += i / len;
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[k];

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

        long answer = 0;
        long lt = 1;
        long rt = max;

        while(lt <= rt) {
            long mid = (lt + rt) /2;
            if(count(mid) >= n) {
                answer = mid;
                lt = mid + 1;
            } else {
                rt = mid - 1;
            }
        }
        System.out.println(answer);
    }
}