<Algorithm> 139. 입국심사(SWExpert)

1. 입국심사(SWExpert)

• 이분탐색 문제

• 이문제를 딱 봤을때 이분탐색 문제일 것이라고 전혀 생각을 못했다.  그리고 N과 M의 크기가 너무커서 완전탐색을 할수가 없었다.

• N과 M의 크기로 힌트를 얻었어야 했는데 아무리 생각해도 어떻게 풀어야 하는지 감이 잡히질 않았다. 

• 내 생각이 DFS, BFS, 완전탐색에만 머물러 있다는 것을 느낀 문제였고 다각도로 접근할 수 있는 시야를 키워야 겠다.

import java.util.Scanner;
 
public class Solution {
    static long[] rooms;
    static long max;
    static long n ;
    static long m;
    static long min;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /******************************
         * 이분탐색을 이용해서 시간을 기준으로
         * 각 방당 수용할 수 있는 인원을 모두 
         * 구하고 필요한 인원을 수용할 수 있는
         * 최소 값을 구한다.
         *******************************/
        int T = sc.nextInt();
        
        for(int t = 1; t <= T; t++) {
            
            n = sc.nextInt();
            m = sc.nextInt();
            max = -1;
            rooms = new long[(int)(n)];
            for(int i = 0; i < n; i++) {
                rooms[i] = sc.nextInt();
                max = Math.max(max, rooms[i]);
            }
            long start = 0;
            long end = max * m;
            min = end;
            
            binary(start, end);
            System.out.println("#"+t+" "+min);
        }
    }
    
    public static void binary(long start, long end) {
        if(start>=end) return;
        long mid = (start + end)/2;
        long capacity = 0;
        
        for(int i = 0; i < n ; i++) {
            capacity += mid/rooms[i];
        }
        if(capacity < m) {
            binary(mid+1, end);
        }else {
            min = Math.min(min, mid);
            binary(start, mid);
        }
    }
}
 

참고 & 출처  

https://wootool.tistory.com/65