Programmers_입국심사

✌️ 기발한 생각으로 풀어내서 내 자신이 뿌듯했는데 다른 사람들도 다 이렇게 풀었더라... 더 열심히 하자

• 필자의 경험상, 숫자의 범위가 10억을 넘어가면 거의 대부분 이분탐색이다.
• 10억이라는 수는 어마무시한 수기에 이분탐색을 안하게 되면 오버플로우
• 그렇다면 이분탐색으로 어떻게 돌릴까 생각을 하다가 return으로 받는 끝나는 시간을 돌리면 어떨까라는 생각을 함.
• 그래서 필자는 return으로 나올수 있는 최댓값을 right에 삽입.

    for (int i = 0; i < times.size(); i++)
        right = max((long long)times[i], right);

    right *= n;

• 이후, 이분탐색을 통해 심사관의 걸리는 시간을 모두 나눠서 더해줌.
• 이 값이 n보다 크다면?? 최적의 값일 수 있으니 일단 mid를 answer에 넣어주고 right = mid -1
• 작다면 당연히 left = mid+1

💻 전체 코드

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long left = 0;
    long long right = 0;
    long long mid = 0;
    
    for(int i=0;i<times.size();i++)
        right = max((long long)times[i], right);
    
    right *= n;
    
    while(left <= right)
    {
        mid = (left + right)/2;
        
        long long sum = 0;
        for(int i=0;i<times.size();i++)
            sum+=(mid/times[i]);
        
        if(sum >= n) {
            right = mid-1;
            answer = mid;
        }
        else left = mid+1;
    }
    
    return answer;
}

Level 3 문제. 더럽지 않은 문제였다.