[코딩테스트 C++] 입국심사

오늘의 문제

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

입국심사

나의 풀이(참고후 풀이)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

모범 답안

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

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());

    long long left = (long long)times[0];
    long long right = (long long)times[times.size() - 1] * n;
    long long answer = right;
    while(left <= right){
        long long mid = (right + left) / 2;
        long long pass = 0;

        for(int i = 0; i < times.size(); ++i)
            pass += mid / (long long)times[i];

        if(pass >= n){
            right = mid - 1;
            if(mid <= answer)
                answer = mid;
        }
        else 
            left = mid + 1;
    }
    return answer;
}

배울점

• 문제 유형이 이분탐색이길래 아.. 뭘 이분탐색하는거야 했는데 이런거였다. 와..
• 최대 시간을 잡은 후 거기서부터 이분탐색을 시작한다.. 그 지점에서의 사람 수를 구하고 더 해야겠으면 위로 아님 아래로 내려간다. 이게 이분탐색이구나
• mid를 구하고 최소값을 구하는 방법을 따로 넣는것이아니라 answer가 저장되면 그때부터는 최소를 찾는것
• start <= end이 될때까지 수행
• 이진탐색을 구현한지 오래되었다고 또 까먹었다. 내일 다시 풀어서 개념을 확인하자

• 또 unsigned long long을 쓰는 문제는 처음봤다.
• long long 의 범위는 -9,000,000,000,000,000,000 ~ 9,000,000,000,000,000,000 정도라고 한다
• unsigned long long은 0 ~ 18,000,000,000,000,000,000 쯤이겠다