프로그래머스 - 입국심사 [C++]

 이 문제는 이분 탐색을 이용해서 푸는 문제이다. 사람의 수가 최대 10억이므로 O(n)으로도 불가능하다. 따라서 O(log n) 시간 정도의 알고리즘이 필요하고, 그래서 이분 탐색이 필요하다.

 

 이 문제의 핵심은 무엇을 이분 탐색의 기준으로 삼느냐인데, 나는 정답으로 제출해야하는 모든 사람이 심사를 받는데 걸리는 시간으로 잡았다. 예시로 나왔던 28을 기준으로 보면, 28 / 7 = 4, 28 / 10 = 2 이므로 둘의 합이 6으로 n과 일치하므로 정답이 나오는 것을 알 수 있었다. 만약 27을 기준으로 보면 27 / 7 = 3, 27 / 10 = 2 이므로 아직 6이 되지 않아 숫자를 늘려야함을 알 수 있다.

 

 주의해야 할 점은 만약 합이 n보다 크더라도 일단 정답으로 넣어야 한다는 것이다. 왜냐하면 정확하게 n으로 떨어지지 않을 수 있기 때문이다. 또한 right의 초기값은 최악의 상황에서의 시간 경과인데, 입국 심사를 기다리는 사람 10억, 심사관 수 1, 심사 시간 10억으로 하면 10억 * 10억 = 1,000,000,000,000,000,000 이 나오는데, 이는 long long 자료형으로 커버할 수 있는 값이므로 이를 right의 초기값으로 삼아야 한다.

 

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long people(vector<int>& times, long long mid) {
    long long result = 0;
    
    for (int& t : times) {
        result += (mid / t);
    }
    
    return result;
}

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    long long left = 1;
    long long right = 1000000000000000000LL;
    
    while (left <= right) {
        long long mid = (left + right) / 2;
        
        long long result = people(times, mid);
        
        if (result >= n) {
            right = mid - 1;
            answer = mid;
        }
        else {
            left = mid + 1;
        }
    }
    
    return answer;
}