(C++) - 프로그래머스(Programmers) : 입국심사 답

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

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

 answer가 될 수 있는 최대 범위를 잘 정해야하는 이분탐색 문제였습니다. 절반 테케에서 시간초과가 계속나 2시간 날렸습니다.^^

 시간초과가 자꾸 뜰 경우 : 자료형의 범위를 초과할 경우 시간초과로 처리하는 것 같습니다. 이거 때문에 이분탐색 로직을 계속 고민하여 시간을 쓸데없이 버렸습니다. 

 

풀이방법 : 걸리는 시간을 찾아야 되는 값이라고 상정한 후 그에 대해 이분탐색을 시행한 결과를 반환하였습니다.

 1. n = (걸리는 시간 / 각 심사대가 심사에 걸리는 시간)의 총합

 2. 해당총합이 n이상일 때 걸리는 시간을 줄여야 함. 그리고 answer는 걸리는 시간과 자신의 값 중 최소값을 선택해야 함.

 3. 해당총합이 n미만일 때 걸리는 시간을 늘려야 함.

 이때 answer가 될 수 있는값은 만약 100,000(10만)명의 심사관이 심사하는데 걸리는 시간이 모두 최댓값이라면 long long이어야 하며 해당 범위에 맞도록 반환형을 조절해줘야 AC를 받을 수 있습니다. 함수의 반환형은 long long이나 받는 인자들의 자료형은 모두 int형이기 때문에 c++같은 type을 선언해야 하는 언어의 경우 자료형의 범위를 신경써 주셔야 합니다.

 

Code : 

#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long
#define MAX 10000000000000;
using namespace std;
 
ll solution(int n, vector<int> times) {
    ll answer = MAX;
    ll timeSize = times.size();
    ll l = 1, r = MAX;
    while(l<=r){
        ll mid = (l + r)/2;
        ll sum = 0;
        for(int i = 0 ; i < timeSize; i++) sum += mid/times[i];
        if(sum>=n){r = mid - 1; answer = min(answer,mid);}
        else if(sum<n){l = mid+1;}
    }
    return answer;
}

 1. solution(100000,{1000000000,1000000000,1000000000}); 답 : 10000000000000

 2. solution(6, {7,10}); 답 : 28
 3. solution(6, {6,10}); 답 : 24
 4. solution(6, {8,10}); 답 : 30
 5. solution(6, {4,10}); 답 : 20
 6. solution(11, {3,4,10}); 답 : 18