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

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43238/solution_groups?language=cpp 

프로그래머스

2. 풀이

처음에 이게 왜 이분탐색 문제일까 고민했다..

완전탐색으로 풀려하니 시간 복잡도에서 시간초과가 날 것 같았다.

그래서 다른 사람들의 풀이를 찾아보니 최소의 경우 (최소 소요시간 1분) ~ 최악의 경우 (제일 오래 걸리는 시간) 사이에서 이분 탐색으로 모든 사람의 심사를 완료하면서 최소의 시간을 찾는 문제였다.

 

그리고 각 심사관이 처리할 수 있는 인원 수의 총합을 구해서 n명의 사람을 모두 커버할 수 있는지 검사한다.

추정 시간 / 각 심사관 소요 시간 = 심사하는 인원 수

만약 위 공식의 총 합이 n보다 작으면 더 많은 시간이 필요하므로 left = mid + 1

반대로 총 합이 n보다 크면 최소의 시간을 찾아야하므로 right = mid - 1

해주어서 최적의 값을 찾는다!!

 

이때 주의할 점은 long long 자료형으로 받아서 실행해야한다!

 

3. 코드

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());
    long long min = 1; //최소 시간 1분
    long long max = (long long)(times[times.size()-1]) * n;   //가장 오래걸리는 경우(최악의 시간)
    long long total;
    long long mid;
    
    while(min <= max){
        mid = (min + max) / 2;
        total = 0;    //총 심사한 인원
        // 각 심사관이 심사하는 총 인원 구하기 -> 빨리 심사하는 순으로 처리
        for(int i=0; i<times.size(); i++){
            total += mid / times[i];
        }
        //1) 총 인원이 n명보다 작으면 더 많은 시간이 필요함.
        //2) 심사한 총 인원이 n명보다 많음 -> 시간을 줄여서 최소로해야 함
        if(total < n){
            min = mid+1;
        }else{
            max = mid-1;
            answer = mid;
        }
        
    }
    
    return answer;
}

*참고

https://woongsin94.tistory.com/185