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

문제 링크

입국심사

 

풀이

이분탐색으로 푸는 문제.. 떠올리는 게 어렵다..

1. 기준은 제일 빠르게 처리하는 1분과 가장 느리게 처리하는 심사관 * n이 될 것이다. 이 둘을 left와 right로 잡는다. 여기서 주의할 것은 long long 타입이기 때문에 right를 만들 때 int * int형으로 곱해져 int형이 나오기 때문에 형변환을 해주어야 함
2. mid는 left와 right의 중간 값을 잡고 이분 탐색을 시작할텐데, 이 기준은 mid시간에서 몇 명의 사람이나 처리할 수 있느냐로 본다.
3. cnt가 n보다 크거나 같으면 right의 범위를 줄여주고 answer를 갱신해주고, 작으면 left의 범위를 키워준다.
4. left의 위치가 right보다 작거나 같을 때까지 반복해준 뒤 answer를 출력한다.

 

코드

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;

    long long left = 1; // 가장 짧게 걸리는 시간
    long long right = (long long)*max_element(times.begin(), times.end())*n; // 가장 길게 걸리는 시간

    while(left<=right)
    {
        long long mid = (left+right)/2;
        long long cnt = 0;

        for(int i=0;i<times.size();i++)
        {
            cnt += (mid/(long long)times[i]);
        }

        if(cnt>=n)
        {
            right = mid-1;
            answer = mid;
        }
        else left = mid+1;
    }

    return answer;
}