<알고리즘 문제풀이&연습>/[C++] 백준

[백준 2023] 신기한 소수

사용자 BlockDMask 2017. 11. 5. 12:26
반응형
  • 안녕하세요!! BlockDMask 입니다!!

  • 오늘의 문제 신기한 소수. 풀어보겠습니다.
    170906 문제 빼먹음 -> 171105 완료

0. 제목

  • 백준 2023 신기한 소수

  • BOJ 2023 신기한 소수

  • prime number

1. 문제 설명

  • 소수 7331을 보면
    7331도 소수이고
    신기하게도 
    733도 소수
    73도 소수
    7 도 소수 입니다.

  • 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다!
    이러한 소수를 신기한 소수라 이름 붙였다.
    N자리의 숫자 중에서 어떤 수 들이 신기한 소수인지 궁금해졌다.
    N이 주어졌을 때, N자리 신기한 소수를 모두 찾아보자.

  • 입력 
    첫째 줄에 N (1<= N <= 8) 이 주어집니다.

  • 출력
    N자리 수 중에서 신기한 소수를 오름 차순으로 정렬해서 한 줄에 하나씩 출력합니다.

2. 풀이 과정

  • 1) 각 자리수의 맨 앞 첫 자리는 한자리 수 소수가 와야하므로 2, 3, 5, 7 만 올 수 있습니다.

  • 2) 첫 자리를 2, 3, 5, 7로 고정한 뒤 첫자리(10*A)와 그다음 자리수(B)를 합친게 소수 인지
    **이때 B는 짝수 이면 2로 나누어져서 소수가 아니므로 홀수를 넣습니다.

  • 3) 그 수가 소수이면 소수인 수 A에 10*A + B 를 한 것이 또 다시 소수인지 쭉쭉 판별하여 자리수가 다할때 까지 진행하면 됩니다.

  • recursive 방식의 dfs 문제로 판단하고 풀었습니다.


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
38
39
40
41
//https://www.acmicpc.net/problem/2023
//BOJ_2023_interestingPrimeNumber
 
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
 
void input(int & n) {cin >> n;}
 
bool isPrime(int num){
    if(num<2return false;
    for(int i=2; i*i<=num; i++){
        if(num%i == 0return false;
    }
    return true;
}
 
void recursive(int first, int n){
    //자릿수(n)가 0이 되면 그 수 출력
    if(n==0printf("%d\n", first);
    
    for(int i=1; i<10; i+=2){   //홀수만 더해주기
        int tmp = first*10 + i;
        if(isPrime(tmp)){
            recursive(tmp, n-1);
        }
    }
 
}
int main(void){
    int n;
    input(n);
 
    //맨 앞 자릿수가 prime number 이어야합니다
    int prime[4= {2357};
    for(int i=0; i<4; i++){
        recursive(prime[i], n-1);
    }
    return 0;
}
cs


4. 인증



문제 출처 - https://www.acmicpc.net/problem/2023

감사합니다.

반응형

'<알고리즘 문제풀이&연습> > [C++] 백준' 카테고리의 다른 글

[백준 2442] 별찍기5  (0) 2017.11.13
[백준 2839] 설탕 배달  (0) 2017.11.12
[백준 2441] 별찍기4  (0) 2017.11.07
[백준 2440] 별찍기3  (0) 2017.11.06
[백준 2023] 신기한 소수  (1) 2017.11.05
[백준 2920] 음계  (0) 2017.11.03
[백준 2615] 오목  (0) 2017.10.31
[백준 2439] 별찍기2  (2) 2017.10.30
[백준 2438] 별찍기1  (0) 2017.10.29