[C++] 백준 23280번: MEX - Math

https://www.acmicpc.net/problem/23820

 

mex(S)는 S에 포함되지 않은 가장 작은 음이 아닌 정수이다.

이 때 mex({ai * aj})를 구하는 문제이다.

 

ai의 범위는 200만 이하의 음이 아닌 정수이고, 곱으로 집합의 원소를 결정하므로 절대로 나올 수 없는 가장 작은 소수는 계산해보니 2000003이다.

그러므로 어떤 수를 곱하던지 상관 없이 2000003을 넘어간다면 즉시 종료하면 되고,

모든 가능한 곱을 다 계산한 이후 0 ~ 2000003까지 나오지 않은 정수를 파악하면 된다.

 

  

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool check[2222222];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    long long x;
    vector<long long>v;
    while(n--){
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=0; i<v.size(); i++){
        for(int j=0; j<v.size(); j++){
            x=v[i]*v[j];
            if(x>2000003) break;
            else check[x]=1;
        }
    }
    for(int i=0; i<=2000003; i++){
        if(!check[i]){
            cout << i;
            break;
        }
    }
}