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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long left = 1;
    long long right = *max_element(times.begin(), times.end()) * (long long)n;
    long long answer = right;
    
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long people = 0;

        for (int time : times) {
            people += mid / time;
            
            if (people >= n) {
                break;
            }
        }

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

    return answer;
}

---

📝 풀이

left는 최소 시간 right는 최대 시간(모든 사람이 가장 오래 걸리는 심사대로 심사 받는 시간)으로 설정합니다.

현재 시간 mid에서 모든 심사대에서 mid / time의 사람을 처리할 수 있는지 계산합니다.

필요한 인원을 충족하면 더 계산 할 필요가 없으니 break 처리를 합니다.

모든 사람을 심사 할 수 있다면 시간을 줄이기 위해 범위를 줄입니다.

그렇지 않다면 모든 사람을 심사 하기 위해 범위를 늘립니다.

최종적으로 최소 시간으로 저장되어 있는 answer을 return 합니다.