260525 다시 풀어봄.

알고리즘 문제 해결 전략

• 최악의 시간복잡도가 나올수 있는 8자리로 생각함.

• 10000000~ 99999999 이고
  - IsPrime의 시간복잡도는 for: 2 ~ 99999999 / 2 이므로
  : 500만이다.
  

-> 결론 : 9천만 번의 타겟 번호를 대상으로 해서 500만을 곱하면됨
=> 시간복잡도 초과다.

다른 방법을 생각해보자.

• 문제의 요구사항이 1번째 자릿수부터 마지막자리까지 소수여야 함.
  -> 즉, 1번째 자리수부터 소수여야 한다!

-> 이를 가지고 2,3,5,7 만 재귀를 하면 된다고 판단했고,
다시 시간복잡도 계산

• 1) 타겟 숫자 4개이고,
• 2) 8줄의 숫자라면 : 8개의 IsPrime 진행
• 3) IsPrime은 500만이므로
  => 4 8 500만 : 4천만 * 4 는 1억 6천만이다.
• 문제의 시간은 2초이므로 가능하다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;

bool IsPrime(int num)
{
	// 2 3 5 7 11 13
	for (int i = 2; i < num / 2; ++i)
	{
		if (num % i == 0)
			return false;
	}

	return true;
}

vector<int> answer;

void dfs(string s)
{
	

	int num = stoi(s);

	if (IsPrime(num))
	{
		if (s.size() == n)
		{
			// Find!! 
			answer.push_back(stoi(s));
			return;
		}

		for (int i = 0; i <= 9; ++i)
		{
			string nextNum = s + to_string(i);
			dfs(nextNum);
		}
	}


}



int main() 
{
	
	cin >> n;

	// 8자리의 숫자 중에서
	// 왼쪽부터 오른쪽 숫자 누적하면서 
	// 진행하는데 모두 소수인 경우는????


	// 만약 7이라고 한다면? 
	// 1000000 ~ 9999999
	// 까지 +1씩을 하면서 의 값을 타겟으로 해서
	// 모두 소수인지를 확인하자. 

	// 7333333 : 예를 들면 왼쪽의 숫자가 해당됨. 

	// 8자리라면
	// 10000000 ~ 99999999
	// 9천만이다.... 간당간당한다.. 

	// IsPrime의 시간복잡도가 
		// for(int i = 2; i < 10000000 / 2; 이므로
		// 5000000

	//9천만 * 5백만은 시간복잡도 초과이다.... 

	// 타겟팅 잡아서 전부다 IsPrime 확인하지 말고, 

	// 솔직히 말해서 
		// 첫번째 숫자부터 소수여야 하므로 

	// 1,2,3,5,7 로만 시작하면 된다.
	// 이렇게만 할 경우의 시간복잡도는 어떨까??

	// 중간의 소수가 안되서 중단되는 경우를 제외한	
		// 최악의 경우를 생각하자.

		// 8줄의 숫자라고 한다면 
		// 8번 확인 * isPrime 500만
		// 4천만이고,

	// 4천만 * 5번의 dfs 이지만,,, 
		// 중도 중단되는 거를 감악하면 2억이고

	// 마침 시간제한이 2억이므로 
		// 위와 같은 방식으로 진행하자.


	
	dfs("2");
	dfs("3");
	dfs("5");
	dfs("7");
	
	for (auto iter : answer)
		cout << iter << endl;
















	return 0;
}