[BOJ 23820] 백준 23820번 - MEX

		2021 POSTECH Programming Open Contest 풀이
A		[BOJ 23813] 회전
B		[BOJ 23814] 아 저는 볶음밥이요
C		[BOJ 23815] 똥게임
D		[BOJ 23816] 옷걸이걸이걸이
E		[BOJ 23817] 포항항
F		[BOJ 23818] 원수의 원수
G		[BOJ 23819] 묻고 더블로 마셔
H		[BOJ 23820] MEX

1. 문제

$23820$. MEX (2021 POSTECH Programming Open Contest H번)

백준 23820번 - MEX (https://www.acmicpc.net/problem/23820)

2. 풀이

혼자 힘으로 해결하지 못했고, 대회 출제진 쪽에서 올려 주신 풀이 슬라이드를 보고 풀었다.

수열의 각각의 수 $x$에 대해서 $1$부터 $2000003/x$ 중 수열에 존재하는 수와의 곱을 모두 체크해주면 된다. 그 다음 ($0$은 나눌 수 없으므로 미리 처리) $1$부터 체크되지 않은 수가 있으면 그 수가 정답이다.

3. 채점 결과

4. 회고

$0$부터 시작해서 없는 소수($0,1$포함)를 찾으면 그게 정답인 줄 알았으나 틀리고 해결하지 못했다. (해설을 보고 풀었기 때문에 이 방법이 틀린 이유는 자세히는 모르겠다.)

처음에 배열에 수가 있는지에 대한 탐색을 set으로 했다가 탐색에 너무 많은 시간을 잡아먹는 것 같아서 단순하게 길이만큼의 check 배열로 방법을 바꾸어 TLE를 해결했다.

5. 코드