문제 푼 날짜 : 2021-09-22

문제

문제 링크 : https://www.acmicpc.net/problem/2023

접근 및 풀이

처음 접근은 N자리수를 나타내는 숫자를 모두 구한 다음 조건에 맞는 수만 걸러내려고 하였다.
하지만, 너무 문제를 만만하게 봤는지 제출하기도 전에 실행하면 뻗어버리는 사태가 나타나서, 이렇게 하면 안되겠다는 생각이 들었다.

그래서 백트래킹의 특성을 살려서 문제의 예시였던 (7 -> 73 -> 733 -> 7331) 처럼 매 자릿수를 추가해주기 전에 소수가 아니라면 어차피 뒤에 어떤 숫자를 붙여도 의미가 없기 때문에 가지치기를 해주었다. 그리고 한 자릿수일때도 소수여야하므로 시작도 2,3,5,7로 시작해주었다.

코드

// 백준 2023번 : 신기한 소수
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int N;

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

void dfs(int cnt, int num) {
    if (!isPrime(num)) {
        return;
    }
    if (cnt == N) {
        cout << num << '\n';
        return;
    }

    for (int i = 1; i <= 9; i++) {
        dfs(cnt + 1, num * 10 + i);
    }
}

int main() {
    cin >> N;
    dfs(1, 2);
    dfs(1, 3);
    dfs(1, 5);
    dfs(1, 7);

    return 0;
}

결과

피드백

백트래킹 설계를 좀 더 신중히하자.