풀이 아이디어

매개변수 탐색

n개의 랜선이 나오는 자르는 단위 길이를 answer라고 하면
가장 긴 단위 길이를 구하는 문제로
매개변수 탐색으로 left,right로 탐색하는 최소 길이, 최대 길이를
n개 이상의 랜선이 나오는 단위 길이 중에서 가능한 최대 길이를 구한다.

• 자른 개수가 n개보다 많거나 작으면
  -> 더 긴 단위길이로 잘라도 되므로
  left = mid+1로 탐색 최소 범위를 갱신해준다.
• 자른 개수가 n개보다 적으면
  -> 더 짧은 단위길이로 잘라야 하므로
  right = mid-1로 탐색 최대 범위를 갱신해준다.

풀이 코드

import java.util.*;
import java.io.*;
public class _1654 {
    static int k; // 이미 가지고 있는 랜선의 개수
    static int n; // 필요한 랜선의 개수
    static int[] lans; // 이미 가진 랜선의 길이를 저장한 배열
    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());
        lans = new int[k];

        int maxLen=0;
        for(int i=0;i<k;i++){
            lans[i]=Integer.parseInt(br.readLine());
            if(lans[i]>maxLen){
                maxLen=lans[i];
            }
        }
        long left = 1;
        long right = maxLen;
        long answer=0; // 랜선의 최대 길이
        long mid=0;
        while(left<=right){
            mid=(left+right)/2;
            // 자른 개수가 N보다 많으면 단위를 더 길게 잘라도 된다.
            if(getCutLines(mid)>=n){
                answer = mid;
                left = mid+1;
            }
            // 자른 개수가 N보다 적으면 단위를 더 짧게 잘라도 된다.
            else{
                right = mid-1;
            }
        }
        System.out.println(answer);
    }
    // unit 단위로 잘랐을 때 나오는 랜선의 개수를 구하는 함수
    static int getCutLines(long unit){
        int cutLines = 0;
        for(int i=0;i<k;i++){
            cutLines += lans[i]/unit;
        }
        return cutLines;
    }
}