2 min to read

Binary Search

이분탐색을 배워봅시다.

Imagem de capa

탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐색하는 것입니다. mid의 값은 (left + right)/2 으로 잡아주고 우리가 검색하고자 하는 값과 mid 값을 비교합니다.

문제를 하나 풀어보죠!

백준 1654번

길이에 대한 정답을 도출해서 이분 탐색으로 끊임없이 탐색해서 결론을 도출하는 것입니다. 즉 길이를 정하고 그 길이에 대한 값으로 랜선을 잘랐을시 그 개수가 원하는 개수보다 크거나 같으면 left를 mid+1 로 반대면 right를 mid-1로 바꾸는 것입니다.


import java.util.Scanner;

public class Main{
    static int K;
    static long N;
    static long first = 0;
    static long last = 2147483647;

    static Long[] line;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        K = scan.nextInt(); // 랜선의 개수
        N = Long.parseLong(scan.nextLine().trim()); // 만들어야 하는 랜선의 개수

        line = new Long[K];

        for (int i = 0; i < K; i++)
            line[i] = Long.parseLong(scan.nextLine().trim());

        System.out.println(lineCal());
    }
    //아래 코드를 분석하면서 생각할 점은 total에 답이 나와도 랜선의 최대길이를 구해야 한다는 점입니다!
    static public long lineCal() {
        long mid = 0;
        while (first <= last) {
            mid = (first + last) / 2;
            int total = 0;

            for (int i = 0; i < line.length; i++) {
                int result = (int) (line[i] / mid);
                total += result;
            }

            if (total >= N)
                first = mid + 1;
            else
                last = mid - 1;
        }
        return last;
    }
}