출처 : https://www.acmicpc.net/problem/2023
신기한 소수 성공
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 4 MB | 1769 | 819 | 603 | 46.780% |
문제
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.
입력
첫재 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.
예제 입력 1
4
예제 출력 1
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
출처
- 문제의 오타를 찾은 사람: uk7880
풀이
dfs를 이용하여 문제를 해결했습니다.
이 문제는 첫 자리부터 연속된 자리 수들이 소수임을 확인해야 합니다.
만약, 현재 자리수가 소수인 것을 확인하면 현재 숫자의 뒷자리에 새로운 숫자를 추가합니다.
그리고 해당 숫자가 소수인 지를 확인해주고 자리 수가 N과 같으면 정답에 추가해줍니다.
이는 dfs 를 구현하면 쉽게 풀 수 있습니다.
소스코드를 통하여 보면 간단하게 확인하실 수 있습니다.
소스코드
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 38 39 40 41 42 43 44 45 | #include <iostream> #include <algorithm> #include <vector> #include <math.h> #define DECI 10 using namespace std; // global int N; vector<int> ans_vec; // 소수 구하는 함수 int is_sosu(int _now_num) { // 루트에 해당하는 값까지 나눠보고 소수인지 체크 for (int div_num = 2; div_num <= sqrt(_now_num); div_num++) if (_now_num % div_num == 0) return 0; return 1; } // dfs 를 통해서 숫자를 갱신한다. void dfs(int _now_num, int _depth) { if (is_sosu(_now_num) == 1) { // 깊이가 N 이 되었으면 리턴 if (_depth == N) { ans_vec.push_back(_now_num); return; } // 소수이면 다음단계로 for (int num = 1; num < DECI; num++) dfs(_now_num * 10 + num, _depth + 1); } else return; } int main() { ios::sync_with_stdio(false); cin >> N; for (int num = 2; num < DECI; num++) dfs(num, 1); int answer_size = ans_vec.size(); for (int vec_idx = 0; vec_idx < answer_size; vec_idx++) cout << ans_vec[vec_idx] << "\n"; return 0; } | cs |