프로그래머스 입국심사 LV3

n명의 대기 인원이 존재할 때 모든 인원을 심사하는 최소 시간을 찾는 문제이다.

제한사항으로 주어진 인원 수와 걸리는 시간이 매우 크기 때문에 이분 탐색을 통해 해결 해야한다.

모든 인원을 심사하는데 걸리는 최소 시간과 최대 시간을 가정한 뒤, 그 값들을 이용하여 시간을 계산해볼 수 있다.

가장 적게 걸리는 시간은 1, 가장 많이 걸리는 시간은 times배열의 가장큰 값에 n을 곱한 값이다.

처음에는 가장 적게 걸리는 시간을 n명의 인원 * 1분의 심사시간인 n으로 책정하고 문제를 풀었는데, 디버그 과정에서 이는 심사관이 1명일 때의 가정임을 깨닫고 최소시간을 1로 수정하였다.

코드를 작성하고 제출했는데 몇 케이스에서 오답이 나와서 고민하다가 질문 게시판을 봤더니, long long을 넘는 오버플로가 발생하는 경우가 있다고 한다.
(참고 링크: https://school.programmers.co.kr/questions/43465)

long long을 unsigned long long으로 변경해서 제출하니 정답이 나왔다.

주어진 값 안에서 하는 이분탐색이 아닌 가능한 시간의 최대와 최소를 이용하여 푸는 문제라 접근이 쉽지 않았는데 타입까지 신경써야하는 문제였다.

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

using namespace std;

unsigned long long solution(int n, vector<int> times) {
    unsigned long long answer = 0;
    
    sort(times.begin(), times.end());
    
    unsigned long long l = 1; // 모든 사람을 처리하는데 걸리는 최소 시간
    unsigned long long r = times.back() * n; // 모든 사람을 처리하는데 걸리는 최대 시간
    
    while(l <= r){
        unsigned long long mid = (l+r)/2; // 모든 사람을 처리하는데 걸리는 평균 시간
        unsigned long long cnt = 0;
        
        for(int i: times){
            cnt += mid/i; // 평균 시간동안 처리할 수 있는 사람의 수
        }
        
        if(cnt >= n){ // 처리가능한 사람의 수가 기다리는 사람의 수보다 많음 -> 처리 시간이 줄어드는 경우도 탐색
            if(answer == 0){
                answer = mid;
            } else{
                answer = min(answer, mid);
            }
            r = mid - 1;
        } else{ // 처리가능한 사람의 수가 기다리는 사람의 수보다 적음 -> 처리 시간을 늘려야함
            l = mid + 1;
        }
    }
    
    return answer;
}