프로그래머스 입국심사 (이분탐색)

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

프로그래머스

1. 특징 

이분탐색

 

2. 구현방법

1) 사람이 10억명, 심사 최대시간도 10억분 이하이다. 따라서 O(n)보다 작은 시간복잡도를 가지는 알고리즘을 써야한다. 이분탐색을 풀면 이문제를 O(logN)으로 풀수 있다. 이분탐색으로 풀기로 했다면, 이분탐색을 하면서, 무슨 값을 찾을 지 설정해야한다. 여기서는 당연히 "모든 사람이 심사를 받는 데 걸리는 최소시간"이다. 

2) st값을 "모든 사람이 심사를 받는데 걸리는 시간의 최솟값"으로 설정한다. 따라서 st = 1

3) en값은 최댓값으로 설정하여, en = n * times 벡터의 최댓값 (ex. 예시에서 6명(n)의 사람이 모두 10분(times 벡터의 최댓값)걸리는 심사관에게 간경우)

4) st <= en일때, 이진탐색을 진행한다. 

5) 이진탐색에서는 mid = (st+en)/2 의 mid 값의 시간동안 몇명이 입국심사(res변수) 받는지 계산한다. 

-> mid가 30이라면 (7분걸리는 심사관: 4명, 10분걸리는 심사관: 3명  따라서 7명이 심사받을 수 있고, 시간을 더줄일수있다)

6) res가 n 이상이라면, mx = mid-1로 설정하고, 현재 mid 값을 answer에 저장. 

이하라면, mn = mid+1 한다. 

 

3. 조심할 점

en = n * (long long)times[times.size()-1]; 을 계산할 때 n * times값이 int형을 넘어갈 수 있다. 따라서 n이나 times를 long long 형으로 바꾸어야한다. 

 

4. 코드

#include <bits/stdc++.h>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());
    long long st = 1;
    long long en = (long long)n * times[times.size()-1];
    
    while(st <= en)
    {
        long long mid = (st + en)/2;
        long long res = 0;
        
        for(int i = 0; i < times.size(); i++)
        {
            res += (mid /times[i]);
        }
        
        if(res >= n)
        {
            en = mid - 1;
            answer = mid;
        }
        else
        {
            st = mid + 1;
        }
    }
    
    return answer;
}