3671. 산업 스파이의 편지

난이도	정답률(_%)
Gold IV	48.163

설계

7자리 수에서 가능한 모든 경우를 판별하고, 소수인지 여부를 검사하며 중복 여부를 체크해야 한다.

소수의 판별은 에라토스테네스의 채를 이용해 진행한다고 하면,

// 에라토스 테네스의 채 시간복잡도
Nlog(logN)

모든 경우를 탐색할 때 시간 복잡도는 7! 이므로 5040번이다.

테스트케이스는 최대 200까지이므로

총 시간 복잡도는

NloglogN + 7! = 10,000,000 * log_2(24) + 5040 * 200 = 51,008,000

이므로 제한 시간 내에 충분하다.

7자리까지의 숫자는 int형으로 충분하다.

따라서 int형으로 선언한다.

이미 방문했는지 여부를 탐색해야 한다.

7자리 숫자는 충분히 작으므로, bool 배열로 이를 체크한다.

dfs로 각 자리수를 탐색할 때마다 생성한 수를 체크한다.

이 때 소수인지 또한 같이 검사한다.

내 코드 (ms)	빠른 코드 (ms)
780	28