백준 1654 - 랜선 자르기 (java/자바) 이분 탐색

문제 출처 : https://www.acmicpc.net/problem/1654

 

---

문제 풀이 :

주어진 랜선의 총 개수 K, 만들어야 할 랜선 개수 N일 때

이분 탐색을 이용해 각 랜선을 쪼개어서  총 N개를 만족하는 최대 랜선 길이를 구해야 한다.

 

 

이진 탐색의 범위는 

low : 1 cm

high : 랜선 배열 중 가장 긴 랜선

 

주의 사항은 랜선 배열의 각 랜선의 길이가 ' 2의31승-1보다 작거나 같은 자연수' 라고 했으므로 

변수 타입을 long 타입으로 지정해주어야 하고,

 

최대 랜선 길이 값이 N개 이상으로 나뉘어질 수 있을 때에만 업데이트 될 수 있도록 해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class boj1654 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K, N = 0; // 랜선의 개수 k, 필요한 랜선의 개수 N
        long[] lans; // 랜선 배열

        String input = br.readLine();
        String[] parts = input.split(" ");

        K = Integer.parseInt(parts[0]);
        N = Integer.parseInt(parts[1]);
        lans = new long[K];

        for (int i = 0; i < K; i++) {
            input = br.readLine();
            lans[i] = Long.parseLong(input);
        }
        
        Arrays.sort(lans);

        // 최대 랜선 길이값 찾기
        long low = 1;
        long high = lans[K-1];
        long maxLan = 0;

        while (low <= high) {
            long mid = (high + low) / 2;
            int divCnt = 0;
            for (int i = 0; i < K; i++) {
                divCnt += lans[i] / mid;
            }
            if (divCnt >= N) { 
            	// N 개 이상 만들 수 있을 때에만 maxLen값 update
                maxLan = mid;
                low  = mid + 1;
            } else {
                high = mid - 1;
            }

        }

        System.out.println(maxLan);




    }
    
}