[백준] 2023 - 신기한 소수 (C++)

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

신기한 소수의 예시는 7331이 있을 때, 7331, 733, 73, 7은 모두 소수이다. 이런 수를 모두 신기한 소수라고 할 때, N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 모두 찾는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 8

 

맨 왼쪽에 있는 수에 숫자를 하나씩 붙여가면서 그 수가 소수이고 N자리라면 출력하면 된다. 맨 왼쪽에 있는 수도 소수여야 하기 때문에 2, 3, 5, 7로 시작할 수 밖에 없다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N 입력받기
2. 백트래킹 함수에 2, 3, 5, 7을 넣어 일의 자리가 소수가 되도록 하고, 뒤에 숫자를 붙이면서 진행
   1. 숫자를 붙였을 때 이 수가 소수라면 유망하므로 백트래킹 함수 진행
3. 종료 조건은 숫자의 자리수가 N과 일치하다면 출력하고 함수를 종료하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• 메모리 초과
  • 99,999,999까지의 모든 소수를 찾아서 표시해두려고 했음 → 최대 8자리 수고 시작하는 숫자(2, 3, 5, 7)도 정해져 있기 때문에 그때 그때 이 숫자가 소수인지 판별하는 함수를 만듦

 

---

정답 코드

#include <iostream>
using namespace std;

int n;

bool prime(int num) {
    for (int i=2; i<=num/2; i++) {
        if (num%i==0) return false;
    }
    return true;
}

void dfs(int num, int dep) {
    if (dep==n) {
        cout << num <<'\n';
        return;
    }

    for (int i=1; i<=9; i+=2) {
        int tmp = num*10+i;
        if (prime(tmp)) dfs(tmp,dep+1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    dfs(2,1);
    dfs(3,1);
    dfs(5,1);
    dfs(7,1);
}