[백준] 2023번 신기한 소수

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

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

 

이 문제는 백트래킹을 사용하라고 한다. 백트래킹은 사실 부루트 포스다. 근데 도중에 인터셉터하는 부분이 있다고 백 트래킹이다. 그게 없다면 순수 부루트 포스 즉, 완전탐색이다. 대표적으로 n과m시리즈가 있다.

 

골드 문제치고는 그렇게 까지 어렵게 느껴지 않았다. 하지만 처음 풀때는 모든 경우가 소수인지 판별하는 함수를 만들어 사용하였다. 하지만 그렇게 되니 시간이 겹겹으로 증가하기 시작했다. 

 

그래서 다른 방법으로 이 문제를 풀어야 되겠다고 생각했다.

 

내가 생각할때 이문제의 핵심은 1) 숫자의 소수여부, 2) 숫자의 추가 라고 생각한다.

여기서 숫자의 추가부분을 생각해보면

총 2가지 방법이 있다. 10을 곱한뒤에 i를 추가하는 방법

string으로 변환한다음 옆에 i를 추가하는 방법 

이렇게 총 2가지다. 당연히 말하면 int만 사용하는게 훨씬 빠를거라 생각한다.  그렇다고 string으로 해도 그렇게 느리지는 않는다. 그래서 string으로 작업했다.

 

#include <bits/stdc++.h>
using namespace std;
int m;

bool notPrime(string n) {
  int num = stoi(n);
  if (num == 1) return true;

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

void go(string n,int index) {
  if (index == m) {
    cout << n << "\n";
    return;
  }

  for(int i = 1; i<=9;i++) {
      string temp = n + to_string(i);
      if (notPrime(temp)) continue;
      go(temp,index+1);
  }


}



int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  cin >> m;  

    go("",0);

 
}

인터넷에서 찾아보니 소수를 판별하는 방법은 총 3가지가 있다. 

첫 번째 방법은 간단히 i<n 으로 범위를 정하는 방법이고

두 번째 방법은 i< n/2; 으로 하는 방법,

마지막은 위 방법이있다고 한다. ㅎㅎ

 

다시 본론으로 들어와서

소수를 구했다고 치자..

근데 코드가 좀 이상하다.  int가 아닌 string을 사용해서 소수를 판별하고 있다. string으로 하면 장점이 코드를 굉장히 많이 단순화 시키는게 가능하다. 그래서 string을 선택하였다.

 

자 여기서 백트래킹이 나온다.

만약에 저 반복문에 없고,

반복문 밖에 재귀가 있다고 한다면 그건 그냥 부루트 포스,

안에 있으면 백 트래킹이다. 

 

이게 왜 돼냐면

1-> 12 -> 123 -> 1234 ....

2 -> 21 -> 215 -> 2153...

 

대충 이런식으로 흘러간다. 그러다가 index가  m가 같아질때가 있다. 그때 각각의 재귀들을 탈출시키면 된다.

간단히 말해 

일반 부루트 포스는 재귀로 이어진 체인은 1개 뿐이지만,

백트래킹은 n개라고 할수 있다.(여기서 n개는 문제와 상관없는 n이다.)

 

이 문제에서는 범위를 1부터 9까지 설정하였는데

0은 무조건 소수가 아니기 때문에 1부터 시작하였다.

 

이 부분도 사람마다 구현이 조금씩 달라질 수 있는데

i+=2로 하는 사람들도 있다. 그 이유는 짝수는 무조건 소수가 아니기 때문이다.

다만 i+=2를 선택하게 되면 맨 앞자리가 2라면 가능해야 하기 때문에 

1의 자리일때 소수인 방법들을 모두 설정해줘야 한다.

2, 3, 5,7 소수가 4개 뿐이기 때문에 이것도 그리 어렵지는 않을 것 같다.

 

하지만 나는 그냥 한번에 시도 하기 위해 i++을 선택하였다.

어차피  범위가 4개더 추가된것 뿐이니 그리 느리지 않을 거라 생각했다.

 

그러면 1일때 12일때 전부 notPrime이라는 메서드로 들어가게 된다.

만약 소수라면 그대로 진행이 될거고

아니라면 i값을 증가 시켜줄 것이다.

 

마지막으로 index를 1씩 증가 시켜주면 된다.

이 메소드를 string이나 int로 return시키는 방법도 고려할 수 있는데

그건... 1개 밖에 나오지 않기 때문에 굳이 할려고 한다면 배열을 사용해야한다고 생각한다.

하지만 배열은 필요 없지.. 왜냐하면 그냥 출력하면 되기 때문이다.

 

즉, 백트래킹은 생각보다 많은 결과가 return된다는 걸 알 수 있다.ㅎㅎ

#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;

vector<long long> MARVEL_P[8];
int N;

bool Prime(long long p){
	long long Sqrt = llround(sqrt(p))+1;
	if(Sqrt>p) Sqrt = p;
	for(long long j = 2; j < Sqrt; j++){
		if(p%j==0) return false;
	}
	return true;
}

void MarvelPrime(){
	MARVEL_P[0].push_back(2);
	MARVEL_P[0].push_back(3);
	MARVEL_P[0].push_back(5);
	MARVEL_P[0].push_back(7);
	for(int i = 1; i < N; i++){
		for(vector<long long>::iterator it = MARVEL_P[i-1].begin(); it != MARVEL_P[i-1].end(); it++){
			for(int k = 1; k < 10; k+=2){
				if(k==5) continue;
				if(!Prime(*it*10+k)) continue;
				MARVEL_P[i].push_back(*it*10+k);
			}
		}
	}
}

int main(){
	scanf("%d", &N);
	MarvelPrime();
	for(vector<long long>::iterator it = MARVEL_P[N-1].begin(); it != MARVEL_P[N-1].end(); it++){
		printf("%lld\n", *it);
	}
}