[백준/C++] MEX (No. 23820)

문제

문제 설명

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 봤을 때, 많은 고민을 했다.

 

잘 생각해보면 조건에서 200만까지만 범위가 정해져있으므로, 정말 최악의 경우 200만 보다 크면서 가장 작은 소수의 범위를 벗어나지 않겠다는 생각이 들었다.

 

그리고 a_i *a_j로 S집합의 수를 나타낼 수 있으므로, a_i * a_j의 계산 값이 200만 보다 크면서 가장 작은 소수의 범위 k보다 작을 때 까지만 체크를 하면 되겠다는 생각이 들었다.

 

(잘 생각해보면 이때의 시간 복잡도는 약 2,000,000/a_i 를 전부 더한 값이므로 적분하면 시간복잡도가 약 nLog(n)의 형태가 된다는 사실을 알 수 있다.)

 

그리고 ai와 aj가 정렬된 상태로 나타난다는 조건이 없는데, 이를 2,000,000 크기의 배열에서 등장했는지 체크를 한 다음 A에 0부터 등장한 순서대로 넣으면 O(n) 의 시간복잡도로 정렬을 할 수 있다.

 

이후 정렬된 A_i *A_j를 계산해 S집합에 들어있는지 체크 처리를 하고 최종적으로 0부터 탐색을 시작해 S집합에 없는 수 중 가장 작은 수를 출력하면 된다.

 

+ 200만 보다 크면서 가작 작은 소수는 2,000,003이다.​

 

 

[아이디어 정리]

1. 등장하는 숫자 a_i * a_j로 집합 S를 나타내므로 조건의 최악의 범위를 생각하면 등장하지 않은 가장 작은 S집합에 없는 수는 소수라는 사실을 알 수 있다.
2.  a_i를 오름차순으로 정렬하면 더 빠르게 계산할 수 있으므로 2,000,000 범위의 배열을 이용해 O(n)으로 A집합을 정렬해 채워 넣는다.
3. 이후 A집합의 i번째 수와 j번째 수를 곱한 값이 2,000,003 보다 작을 때 체크를 하고 만약 2,000,003보다 크다면 탐색을 중지하고 다음 i+1번째 수로 나타낼 수 있는 S집합을 체크하도록 넘어간다.

 

 

 

Code

 

 

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

long long maxNum = 2000005;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int tN;
	cin >> tN;
	vector<bool> visit(maxNum+1, false);
	long long num;
	int N=0;
	for (int i = 0; i < tN; i++) {
		cin >> num;
		if (!visit[num]) {
			N++;
		}
		visit[num] = true;
	}
	vector<long long> A(N);
	int idx = 0;
	int ai = 0;
	while (idx < N) {
		if (visit[ai]) {
			A[idx] = ai;
			idx++;
		}
		ai++;
	}

	if (A[0] != 0) {
		cout << 0;
		return 0;
	}

	long long tmp;
	for (long long i = 1; i < N; i++) {
		for (long long j = i; j < N; j++) {
			tmp = A[i] * A[j];
			if (tmp >= maxNum) {
				break;
			}
			else
			{
				visit[tmp] = true;
			}
		}
	}
	for (long long i = 1; i < 2000004; i++) {
		if (!visit[i]) {
			cout << i;
			return 0;
		}
	}

	return 0;
}

 

---

 

처음에 아무리 해도 안되고 Out of Bound에러가 계속 등장했다.

알고보니 a_i를 입력받을 때, 입력받은 숫자가 겹치지 않는다 라는 조건이 없어서 그런 것이었다.

 

진짜 풀려야 하는데 안 풀려서 공부하다 집 갈뻔했다

 

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