[백준] 1654번 : 랜선 자르기

랜선 자르기

---

해결 방법

이 문제 또한 완전 탐색으로는 시간초과가 나는 문제이다.
그래서 이분탐색으로 해결한 문제이며, 조심할 부분은 다음과 같다.

이분 탐색 문제에서는 인덱스의 값을 찾는 문제가 대부분이였다.
하지만 이번 문제에서는 인덱스의 각 값들을 이용해서 최대 랜선의 길이를 구하는 문제였다.

조금 응용만 하면 쉽게 해결할 수 있던 문제였다!

---

코드

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

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());
        long[] lan = new long[k];
        for(int i=0;i<k;i++){
            lan[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(lan);
        System.out.println(binarySearch(n,1,lan[k-1],lan));

    }
    public static long binarySearch(int target,long min, long max,long[] lan){
        long result=0;
        while(min<=max){
            long mid = (min+max)/2;
            long count=0;
            for(long n : lan){
                count+=(n/mid);
            }
            //잘라서 나온 랜선의 개수가 원하는 값보다 작을 때
            //-> 자르는 값을 더 줄여야 함. = max를 줄여야 함
            if(count<target){
                max = mid - 1;
            }
            else{
                result=mid; //현재 mid 값이 잠재적 결과
                min = mid + 1;
            }
        }
        return result;
    }
}