[boj] 백준 1654 랜선 자르기 (Java) - 이분탐색

[문제]

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

1654번: 랜선 자르기

 

[풀이]

기본 이분탐색 문제이다. 다만 주의해야 할 점은 랜선의 최대 길이가 2^31-1 이기 때문에 low, mid, high 값을 long으로 선언해주어 오버플로우가 발생하지 않게 해야 한다.

 

[코드]

 

package 이분탐색;

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

public class boj_1654_java {
    //k개의 랜선을 잘라서 n개의 랜선을 만들고자 할 때, 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성
    static int n, k;
    static int[] lines;
    static long answer;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        lines = new int[k];
        for(int i=0; i<k; i++){
            lines[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(lines);

        long low = 1;
        long high = lines[k-1];
        while(low<=high){
            long mid = (low+high)/2;

            int cnt = divideLine(lines, mid);
            
            if(cnt >= n){ //n개 이상의 랜선을 만들 수 있다면 랜선 길이를 늘림
                answer = mid; 
                low = mid+1;
            }
            else{ //만들 수 없다면 랜선 길이를 줄임
                high = mid-1;
            }
        }

        System.out.println(answer);
    }

    public static int divideLine(int[] lines, long mid){
        int cnt = 0;
        for(int l:lines){
            cnt += l/mid;
        }
        
        return cnt;
    }
}