백준 BOJ 1654번

 

---

접근 방법

 

생각없이 0번부터 탐색하는 burte force 방식으로 구현하면 어김없이 시간초과를 맛 볼 것이다.

 

이분 탐색으로 풀어야 하는 문제다.

 

이분 탐색( Binary Search )

이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다.

배열이 정렬되어 있어야만 사용할 수 있다. 이분 탐색할 때 세 개의 변수가 쓰이는데, low, high, mid 다.

• low & high → low 또는 left 는 시작점을, high 또는 right는 끝점의 인덱스를 가리킨다.
• mid → 탐색 범위의 중간값으로 실질적으로 검사하는 변수이다. mid와 찾고자하는 값을 비교해서 다음 탐색 범위를 설정한다.

 

과정

1. 탐색 범위에서 mid를 설정하고 target과 비교한다.
2. mid == target 이라면 해당 값을 반환한다.
3. mid < target 이라면 탐색 범위를 큰 쪽으로 변경한다. ( low = mid +1 )
4. mid > target 이라면 탐색 범위를 작은 쪽으로 변경한다. ( high = mid -1 )
5. 1~4번을 반복한다.

출처: www.penjee.com

위의 그림을 보면 쉽게 이해할 수 있다.

 

---

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int K = in.nextInt();
        int N = in.nextInt();

        int[] arr = new int[K];

        long max = 0;

        for (int i = 0; i < K; i++) {
            arr[i] = in.nextInt();
            if(max < arr[i]) {
                max = arr[i];
            }
        }
        max++;

        long min = 0;
        long mid = 0;

        while (min < max) {
            mid = (max + min) / 2;
            long count = 0;
            for (int i = 0; i < arr.length; i++) {
                count += (arr[i] / mid);
            }
            if(count < N) {
                max = mid;
            }
            else {
                min = mid + 1;
            }

        }
        System.out.println(min - 1);
    }
}