Easy is Perfect

[백준] 2023번 C/C++ 풀이 _ 신기한 소수

  • melonicedlatte
  • Sep 09, 2018


출처 : https://www.acmicpc.net/problem/2023 

신기한 소수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초4 MB176981960346.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



Search