[BOJ][백트래킹][골5][1759] 암호 만들기

문제 링크

문제 링크

풀이

알고리즘

N자리 K진수를 적용해서 해결하는 문제입니다.

• 서로 다른 알파벳 L개
• 최소 모든 1개, 최소 자음 2개
• 알파벳이 증가하는 순서로 배열

배열을 사용한 정답 코드

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

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

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진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.