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

문제 링크: programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

1. 주의할 점

- 이분탐색으로 해결한다

- Right 포인터의 값이 Int값을 벗어날 수 있다 (Long Long으로 형변환 필요) -> 8번 TC

 

2. 구현

- Tip) Mid의 값을 구할 때 Left+(Right-Left)/2로 한다. Right+Left/2로 할 경우, Int 혹은 Long Long의 범위를 벗어나면 음수값이 저장되므로 사전에 예방한다.

- 해당 값(Mid)을 기준으로 각 심사관이 검사할 수 있는 사람의 수를 구한다(Mid/ 심사관이 1명 검사하는 데 소요되는 시간)

- 모든 심사관들들이 검사할 수 있는 사람의 수를 Temp에 더하고 Temp>=N이라면 더 적은 시간으로도 가능한지(Mid를 낮춘다) 확인해보기 위해 Right 포인터의 값을 Mid-1로 설정한다. Temp<N이라면 시간이 부족하므로 Mid의 시간을 늘리기 위해 Left 포인터의 값을 Mid+1로 설정한다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());    
    long long l=times[0],r=(long long)times[times.size()-1]*(long long)n,mid;
    while(l<=r){
        mid = l + (r-l)/2;
        long long temp = 0;
        for(int i=0;i<times.size();i++)
            temp+=(mid/times[i]);
        if(temp>=n){
            answer=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return answer;
}