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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

이분탐색으로 해결한 문제이다. 초기 값으로 left를 1, right는 times 중의 최댓값 x n으로 설정하고 이분탐색을 하였다. mid = (left + right) / 2라고 하면 mid / times[i] 값은 mid 시간동안 i번째 심사관이 검사할 수 있는 사람의 수이므로 검사할 수 있는 사람의 수를 모두 더한 값과 n을 비교하며 이분탐색하면 해결할 수 있다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = numeric_limits<long long>::max();
    sort(times.begin(), times.end());
    long long left = 1;
    long long right = (long long)n * times[times.size() - 1];

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

        long long cnt = 0;
        for (int t : times) {
            cnt += (mid / t);
        }

        // n명을 모두 처리한 경우
        if (cnt >= n) {
            answer = min(answer, mid);
            right = mid - 1;
        }
        // n명을 처리하지 못한 경우
        else {
            left = mid + 1;
        }
    }
    return answer;
}