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

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

프로그래머스

이분탐색 문제이다.

 

다만 이 문제가 좀 까다로운 점은, 도대체 뭘 탐색해야 할까? 에 대한 물음일 것이다.

 

최악의 경우를 따져보았을 때, 걸리는 시간이 너무 커서 탐색할 엄두도 안나겠지만, 이분탐색은 log n의 시간 복잡도를 가지므로 충분히 해결할 수 있다.

 

다른 이분탐색 코드와 다른 점이 있다면,

1. 개인의 심사원이 주어진 시간(mid)동안 처리할 수 있는 손님의 수를 구하는 코드

2. 예를 들어, 처리해야 할 손님이 10명이라 하자

28분에는 9명밖에 처리를 못하는데, 29분에는 11명을 처리할 수 있다면 어떻게 될까

손님은 11명이 아니라 10명뿐 이지만, 모두 처리할 수 있는 최소 시간을 구하는 것이므로 29분이 답이 될 것이다.

 

현재 처리한 인원의 수(=cnt)가 처리해야 할 인원의 수(=n)보다 클 경우에, 이분 탐색의 범위를 줄여주면서 

동시에 현재 주어진 시간(=mid)를 정답으로 처리해준다.

 

이 문제의 경우, 반드시 답이 있다고 가정되어 있기 때문에 이분 탐색이 종료되는 순간에 answer에는 우리가 원하는 답이 들어 있을 것이다.

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 1e18;
    long long low = 0;
    long long high = 1e18;
    long long mid = 0;

    while(low <= high){
        mid = (low+high)/2;
        long long cnt = 0;

        for(int i=0; i<times.size(); i++){
            cnt += mid / times[i];
        }
        
        if(cnt < n) low = mid+1;
        else{
            high = mid-1;
            answer = mid;
        }
    }
    return answer;
}