반응형
https://www.acmicpc.net/problem/2023
2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
[ 문제풀이 ]
1. 첫번 째 자리 숫자는 소수여야 하므로 2, 3, 5, 7 밖에 들어가지 못합니다.
2. 다음 자리 숫자부터는 짝수가 들어가면 소수가 되지 못하므로 홀수만 넣어주고, 소수 판별을 통해 소수인지 체크해줍니다.
3. 백트래킹을 통해 반복하면서 소수라면 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include<iostream> #include<cmath> using namespace std; bool isPrime(int num){ if(num<2) return false; for(int i=2; i*i<=num; i++){ if(num%i == 0) return false; } return true; } void dfs(int first, int n){ //자릿수(n)가 0이 되면 그 수 출력 if(n==0) printf("%d\n", first); for(int i=1; i<10; i+=2){ //홀수만 더해주기 int tmp = first*10 + i; if(isPrime(tmp)){ dfs(tmp, n-1); } } } int main(void){ int n; scanf("%d", &n); //맨 앞 자릿수가 prime number 이어야합니다 int prime[4] = {2, 3, 5, 7}; for(int i=0; i<4; i++){ dfs(prime[i], n-1); } return 0; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 20311번 - 화학 실험 (C++) (0) | 2023.04.21 |
|---|---|
| [ 백준 ] 11562번 - 백양로 브레이크 (C++) (0) | 2023.04.20 |
| [ 백준 ] 2602번 - 돌다리 건너기 (C++) (0) | 2023.04.18 |
| [ 백준 ] 1507번 - 궁금한 민호 (C++) (0) | 2023.04.17 |
| [ 백준 ] 2668번 - 숫자고르기 (C++) (0) | 2023.04.16 |