[이분탐색] 입국심사

|| 문제설명 ||

1. n명이 입국심사를 위해 줄을 서서 기다리고 있다.
2. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르다.
3. 처음에 모든 심사대는 비어있다.
4. 한 심사대에서는 동시에 한 명만 심사를 할 수 있다.
5. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다.
6. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶다.
7. 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성하라.

• n : 입국심사를 기다리는 사람 수
• times : 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열

_ 입국심사를 기다리는 사람(n) : 1명 이상 1,000,000,000명 이하
_ 각 심사관이 한 명을 심사하는데 걸리는 시간(times) : 1분 이상 1,000,000,000분 이하
_ 심사관(times.size()) : 1명 이상 100,000명 이하

---

|| 문제해결방법 ||

---

|| 코드 ||

[2020.09.11] 실패

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    vector<int> chk;
    
    for(int i=0; i<times.size(); i++) {
        for(int j=1; j <= n - i; j++) {
            chk.push_back(times[i]*j);
        }
    }
    sort(chk.begin(), chk.end());
    answer = chk[n-1];
    return answer;
}

• 메모리 초과 : 알고리즘 자체가 문제에 적합하지 않음.

---

[2020.09.11] 실패

- 이분탐색 알고리즘 적용

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer, left, right ;

    sort(times.begin(), times.end());
    
    left = times[0]*n/2; 
    answer = right = times[times.size()-1]*n/2;
    
    while(left <= right) {
        long long mid = (left + right) / 2, cnt = 0;
        for(auto i : times) {
            cnt += mid / i;
        }
        if(cnt < n) left = mid;
        else if(cnt > n) right = mid;
        else {
            if(mid < answer) answer = mid;
            left++; right--;
        }
    }

    return answer;
}

• else 문에서 left++;right--; 은 결국 제자리 걸음일 뿐이다.

→ cnt == n인경우 그 앞뒤로 세세한 결과를 보고 싶다면 +1/-1을 해야하는데 기존의 알고리즘으로는 불가능하다.

(같을 경우에도 변화를 줘서 다음으로 넘어가게 해줘야하는데 이를 위해서는 작을 경우나 클 경우와 합쳐야 하고 변화를 줘야함)

작은 경우 보다는 큰 경우를 같을 때와 합치고 left = mid+1 로 변경하여 변화를 줌

if(cnt < n) 
	min = mid + 1;
else {
        if(mid < answer) answer = mid;
        max = mid - 1;
}

---

[2020.09.12] 실패

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer, min, max;

    sort(times.begin(), times.end());
    
    min = 0; 
    answer = max = times[times.size() - 1] * n;
    
    while(min <= max) {
        long long mid = (min + max) / 2, cnt = 0;
        for(auto i : times) {
            cnt += mid / i;
        }
        if(cnt < n) min = mid + 1;
        else {
            if(mid < answer) answer = mid;
            max = mid - 1;
        }
    }
    return answer;
}

---

[2020.09.12] 성공

- max 의 타입은 long long이지만 맨처음 초기화 시켜줄 때 times[times.size() - 1]]과 n은 int 타입이기에 강제 형변환이 필요하다.

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer, min, max;

    sort(times.begin(), times.end());
    
    min = 1; 
    answer = max = (long long)times[times.size() - 1] * (long long)n;
    
    while(min <= max) {
        long long mid = (min + max) / 2, cnt = 0;
        for(auto i : times) {
            cnt += mid / i;
        }
        if(cnt < n) min = mid + 1;
        else {
            if(mid < answer) answer = mid;
            max = mid - 1;
        }
    }
    return answer;
}