반응형
신기한 소수
-
BOJ) 신기한 소수알고리즘/백준 2020. 7. 21. 15:15
신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수� www.acmicpc.net 풀이 처음에는 모든 숫자에 대해 DFS를 진행하면서 답을 구하려고 시도했다. 하지만 문제의 최대 조건인 n=8인 경우에 엄청난 시간이 소요되면서, 가지치기가 더 필요한 것을 느꼈다. 문제의 조건을 자세히 봤다. n=4 인 경우에 나오는 수를 살펴보면, 첫번째 자리에는 {2,3,5,7} 만 오고 나머지 자리에는 {1,3,7,9}만 나와있음을 확인했다. 이 말은, n=3인 경우, n=2인 경우에도 앞의 자리가 위의 네가지 숫자 말고는 올 수..