Uncategorized

[알고리즘/이진탐색] 프로그래머스, 입국 심사 문제

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        //n은 1억이하, times의 요소는 1억 이하, times의 개수는 10만개이하.
        //1. 풀이
        //2. 코드 검토
        //3. Overflow 검토
        
        long l = 0;
        long r = (long)times[times.length-1] * n;
        
        long least = Long.MAX_VALUE;
        while(l<=r) {
            long m = (l+r)/2;
            
            long c=0;
            for(int t : times) c += m/t;
            
            if(c>=n) {
                r = m;
                if(least > r) least = r;
                r -= 1;
            } else {
                l = m;
                l += 1;
            }
        }
        
        return least;
        
    }
}
https://github.com/imkim1893/algorithms/blob/master/%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.java