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

문제

---

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

 

풀이

---

처음에 문제풀이 방법을 떠올리기 쉽지 않은 문제다.

풀이 시 다음 사람을 어떤 심사관에 배정할까 ? 라는 의문으로 시작하면 가능한 방법이 떠오르지 않는다.

이 문제는 파라메트릭 서치 개념을 사용해서 풀이할 수 있다.

파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어서 풀이하는 개념이다.

이 문제의 경우 "심사시간이 주어졌을 때, N명의 사람을 모두 심사할 수 있는가?" 라는 내용으로 주어진 시간 범위 내에서 이분탐색을 진행하며,

N명의 사람을 심사할 수 있는가? 를 확인 후 N명의 사람을 모두 심사할 수 있는 시간들 중 최소값을 정답으로 결정하면 된다.

 

소스 코드

---

 

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

const long long MAX_TIME = 1e9;

using namespace std;

long long solution(int n, vector<int> times) {
    
    sort(times.begin(), times.end());
    
    long long maxTime = MAX_TIME * n; // 최대 소요시간
    
    long long left = 1, right = maxTime;
    long long cntOfExamined = 0;
    
    while(left <= right){
        
        long long mid = (left + right) / 2; // 현재 시간
        
        cntOfExamined = 0; // 현재 시간이 mid일 경우 심사가능한 사람 수
        for(const auto time : times)
            cntOfExamined += mid / time;        
        
        // 심사한 사람의 수가 N명보다 크거나 작으면 시간을 줄여본다
        if(cntOfExamined >= n)
            right = mid - 1;
        else
            left = mid + 1; 
        
    }
    
    return answer = left;
}