[BOJ][백트래킹][골5]][2023] 신기한 소수

문제 링크

문제 링크

풀이

알고리즘

N자리 K진수를 적용해서 해결하는 문제입니다. N자리 K진수의 개념은 그대로 적용되고 핵심은 두 가지 입니다.

1. isPrime()을 작성할 수 있는가? -> 소수인지 판별하는 O(sqrt(n)) 방법을 사용합니다.
2. isPrime()을 적절한 위치에서 사용할 수 있는가? -> recur()의 초입 부분에 적용해서 사용합니다.

배열을 사용한 정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n = 0, k = 0; //N:배열의 길이 , K: 진수
int v[8];
bool visited[100];

bool isPrime(int depth) {
  // v가 depth-1까지 채워진 상태
  if (depth == 0) return true;
  int num = 0;
  for (int i = 0; i < depth; i++) {
    num *= 10;
    num += v[i];
    // 0,1은 소수가 아님
    if (num <= 1) return false;
    int cnt = 0;
    for (int j = 2; j * j <= num; j++) {
      if (num % j == 0) cnt++;
    }
    if (cnt) return false;
  }
  return true;
}

void recur(int depth) {
  if (!isPrime(depth)) return;
  if (depth == n) {
    for (int i = 0; i < n; i++) {
      cout << v[i];
    }
    cout << "\n";
    return;
  }
  // i가 0인 경우 0 또는 10의 배수가 되어 소수가 되지 못한다.
  for (int i = 1; i <= 9; i++) {
    v[depth] = i;
    recur(depth + 1);
  }
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  //배열의 0번쨰 index부터 채우기 시작해야한다.
  recur(0);

  return 0;
}

파라미터를 사용한 두 번째 풀이

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n = 0, k = 0; //N:배열의 길이 , K: 진수
int v[8];
bool visited[100];

bool isPrime(int curr) {
  // 한 번 들어온 curr는 다시 들어오지 않는다.
  if (curr == 0) return true;
  else if (curr == 1) return false;
  int cnt = 0;
  for (int i = 1; i * i <= curr; i++) {
    if (curr % i == 0) cnt++;
  }
  return cnt == 1;
}

void recur(int depth, int curr) {
  if (!isPrime(curr)) return;
  if (depth == n) {
    cout << curr << "\n";
    return;
  }

  // i가 0인 경우 0 또는 10의 배수가 되어 소수가 되지 못한다.
  for (int i = 1; i < 10; i++) {
    recur(depth + 1, curr * 10 + i);
  }
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  //배열의 0번쨰 index부터 채우기 시작해야한다.
  recur(0, 0);

  return 0;
}

Success Notice: N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.