프로그래밍스 > 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238

1. 알고리즘은 거진 모든 경우의 수를 탐색하되, 그 중 가능하며, 가장 효율적인 방법을 찾아서 선택해야 한다.

2. 실제 사람이 해결하는 방법을 따라가며 해결해야할 수도 있지만, 수학적으로 생각해서 해결할 수도 있어야 한다. 이 문제의 경우, 수학적으로 최적점을 찾고, binary search를 통해 이를 효율적으로 찾는다.

3. Array를 sorting한 다음, processedSum += mid / time; 로 가장 짧은 시간으로 최대한 처리하며 넘어갔을 때, 최적점이 나오는 것을 비교해 수학적으로 해결한다.

4. 문제 내용 중 1,000,000,000분이 나오고, 이를 곱하며 사용하기 때문에 (27억이 넘음) long을 사용해야한다.

import java.util.*;

class Solution {
public long solution(int n, int[] times) {
long answer = Long.MAX_VALUE;

    Arrays.sort(times);
    
    long left = 0;
    long right = (long) n * times[times.length-1]; // worst case
    
    while(left <= right) {
        long mid = (left+right)/2;
        long processedSum = 0;
     
        for(int time : times) {
            processedSum += mid / time;
        }
        
        if(processedSum < n) {
            left = mid + 1;
        } else {
            answer = Math.min(answer, mid);
            right = mid - 1;
        }
    }
    
    return answer;
}

}