[알고리즘] 백준 2023번: 신기한 소수 (C++), 음..? 신기한 문제네

---

논리

입력으로 4가 주어지면 4자리 수 중에 예를 들어 7331이면 맨 앞자리부터 7, 73, 733, 7331처럼 모두 소수가 되어 만족하는 수들을 구하는 문제였다.

 

논리를 이렇게 짜두고 코드는 반대로 7331, 733, 73, 7 순서로 소수인지 판별했다.

하지만, 이는 시간 초과를 유발한다.

 

그래서 반대로 맨 앞자리부터 소수 판정을 하는 코드를 짰다.

왜냐하면 극단적으로 8자리 수가 주어졌을 때, 8자리 수가 소수인지 판정을 하고 7자리 수가 소수인지 판정하는 것보다는 1자리 수가 소수인지 판정하고 그다음으로 넘어가는 형식이 더 빠르기 때문이다.

 

그래서 다음과 같이 코드를 짰다.

(맨 처음의 수를 기억하고 있어야 하기 때문에 solution 함수에서 answer에 초기값을 넣어줬다.)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int answer = 0;
int save = 0;

bool isPrime(int n) {
	if (n == 1) {
		return 0;
	}
	if (n == 2) {
		return 1;
	}
	for (int i = 2; i < sqrt(n) + 1; i++) {
		if (n % i == 0) {
			return 0;
		}
	}
	return 1;
}

void solution(int n, int cnt, int val) {
	if (val != 0 && n / val == save) {
		return;
	}

	if (cnt == 0) {
		answer = n;
	}

	if (val == 0) {
		cout << answer << '\n';
		return;
	}

	if (isPrime(n / val) == true) {
		val /= 10;
		solution(n, cnt + 1, val);
	}
	else {
		save = n / val;
		return;
	}
}

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

	int n;
	cin >> n;
	int val = pow(10, n - 1);
	int val2 = pow(10, n);

	for (int i = val; i < val2; i++) {
		solution(i, 0, val);
	}

	return 0;
}

---

어라

이 포스팅을 하는 이유가 원래 isPrime에 n == 0일 때도 return 1을 하니까 정답이 되길래 포스팅을 쓰고 있던 건데 어쩌다가 시간 초과가 뜬 코드를 다시 제출했더니 맞다는 결과가 나왔다. (당황스럽네)