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

문제

---

 

프로그래머스

 

 

풀이

---

이번 문제도 이분탐색이다.

이분탐색이 들어가긴 하나 적용 방식은 조금 다르긴 하여 매개변수 탐색이라고도 부른다.

 

우선 문제를 요약하면 이렇다.

심사 대상자가 있고 심사관이 있는데, 심사관들의 심사 시간은 제각각이다.

심사관들의 심시 시간은 `times` 배열로 들어온다. ▼

 

하나씩 차근차근 심사 대상자들을 심사관에게 배정을 해보면 최적의 시간을 찾을 수는 있으나, 심사관의 수가 매번 다르게 들어오기 때문에 분배를 할 때 생각할 것이 많아진다.

이렇게 심사 대상자들을 심사관에게 직접 배정하면 문제를 처리하는 과정이 일관적이지 않게 되는 문제가 발생한다. ▼

 

하지만 반대로 "이만큼의 시간을 줄테니 이 시간 내로 심사관들이 처리할 수 있을까?" 라는 질문의 해답은 쉽게 얻을 수 있다.

즉, 이론적으로 가장 오래 걸리는 시간부터 최소 시간 사이의 시간들을 검증하면 해답을 구할 수 있다는 것이다.

 

그렇다면 이론적으로 가장 오래걸리는 시간을 구하면 되는데, 범위에 조심해야한다.

사람 수의 최대값과 검사 시간의 최대값을 곱하면 이론상 가장 오래걸리는 시간이 되는데, 이 값이 `long long` 범위를 초과한다.

그러니 `unsigned long long`으로 처리해야한다. ▼

 

그 뒤는 이분탐색을 사용하면 쉽게 해결이 된다. ▼

 

 

C++ 코드

---

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    
    unsigned long long maxValue = n * times.back();
    unsigned long long answer = 0;
    unsigned long long left = 0;
    unsigned long long right = maxValue;
    
    while (left < right) {
        long long cnt = 0;
        long long mid = (left + right) / 2;
        
        for (long long i = 0; i < times.size(); i++) {
            cnt += mid / times[i];
        }
        
        if (cnt < n) {
            left = mid + 1;
        } else {
            right = mid;
            answer = mid;
        }
    }
    
    return answer;
}