알고리즘77 :: 이분탐색이란? BOJ_13702에 적용

이분탐색이란?

데이터를 반씩 탐색하여 O(logN) 으로 찾아갈 수 있다. 단, 이분탐색은 정렬된 상태에서 쓸 수 있다.

 

이분탐색원리

low, high 가 있어서 low<=high 조건 아래에서 찾고자 하는 data가 나타날 때 까지 이분탐색 한다. 이때, data가 찾고자 하는 값보다 작다면 low 를 mid + 1 로 크다면 high를 mid -1로 설정한다. 

 

이 문제에서 어떻게 적용될까?

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

크게 보면 다음과 같다. 

각 주전자에 따라진 술들을 배열의 인덱스로 저장한다. ex) pots[0] = 주전자1, pots[1] = 주전자2, pots[2] = 주전자3

그리고, 0부터 최대 2의31승-1 (=4,294,967,295) 전체를 보며 모두에게 나눠줄 수 있는 술의 최대량을 보면 되는데.. 숫자가 굉장히 크다. 

 

따라서, 이분 탐색하며 찾아본다면 2의 15승-1(=32,767) 만에 찾을 수 있다. 

 

코드 및 솔루션

 

package backjun;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class 이상한술집 {
 
    static int[] pots;
    static int n;
    static int k;
    static boolean valid(int nn) {
        int cnt = 0;
        for(int i=0; i<n; i++) {
            cnt+=pots[i]/nn;
        }
        if(cnt>=k)
            return true;
        else
            return false;
    }
    static int go() {
        int low = 0; 
        int high = Integer.MAX_VALUE;
        while(low<=high) {
            int mid = (low+high)/2;
            if(valid(mid)) {
                low = mid + 1;
            }else {
                high = mid-1;
            }
        }
        return high;
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        pots = new int[n];
        for(int i=0; i<n; i++) {
            pots[i] = Integer.parseInt(br.readLine());
        }
        int r = go();
        if(r==-1)
            System.out.println("0");
        else
            System.out.println(r);
    }
 
}