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

이분 탐색을 어떻게 사용해야할 지 떠올리기 정말 힘들었던 문제이다.

그리고 오버플로우도 주의해야 한다.

 

 

n	times	return
6	[7, 10]	28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

이분 탐색을 하려면 특정 값의 low와 high를 정해야 한다. 이 문제에서 특정 값은 전체 심사 시간이 될 수 있다.

이 문제는 심사관이 가장 오래 심사하게 되는 시간을 high로 정하는 게 핵심이라고 생각한다.

그리고 low 값은 `각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.` 라는 조건이 있기 때문에 1로 설정할 수 있다.

 

위 예시에서는 가장 오래 심사하는 시간은 6 * 10 = 60 분이다.

이때 mid값은 (1 + 60) / 2 = 30이 되고, 30시간동안 30/7 + 30/10 = 7명의 사람을 심사할 수 있다.

 

우리가 원하는 값인 n인 6보다 많은 사람을 심사할 수 있으므로 전체 심사시간을 줄여야 한다.

-> high = mid-1 을 수행한다.

그리고 현재 심사시간인 mid를 가지고 answer를 갱신한다. (둘 중 작은 값으로 answer를 갱신)

마찬가지로 원하는 n보다 적은 사람을 심사하게 되면 low = mid + 1 을 수행해서 범위를 절반 씩 줄여나가면 된다.

 

10억 * 10만 = 1e14 이므로 answer의 초기값을 1e14 + 1로 잡아주어야 한다. (1e13도 통과되긴 한다.)

 

로직은 맞는데 자꾸 여러 테스트 케이스에서 틀렸다고 나왔다.

long long -> unsigned long long 으로 바꾸니까 AC를 받을 수 있었다. 

high로 나올 수 있는 최댓값인 10억 * 10억을 해도 long long 범위 안 인데 이유 모를 오버플로우가 있었나보다.

 

 

최종 코드

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

typedef unsigned long long ll;

using namespace std;

ll solution(int n, vector<int> times) {
    ll answer = 1e14 + 1;
    
    sort(times.begin(), times.end());
    
    ll low = 1;
    ll high = times.back() * n;
    
    while(low <= high){
        ll mid = (low + high) / 2;
        ll check = 0;
        
        for(int i = 0; i < times.size(); i++){
            // mid 시간 안에 심사할 수 있는 최대 사람 수
            check += (mid / times[i]);
        }
        
        if(check >= n){
            high = mid - 1;
            answer = min(answer, mid);
        }
        else{
            low = mid + 1;
        }
    }
    
    return answer;
}