PS/BOJ
[알고리즘] 백준 2023번: 신기한 소수 (C++), 음..? 신기한 문제네
도비(Doby)
2021. 10. 1. 08:56
논리
입력으로 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을 하니까 정답이 되길래 포스팅을 쓰고 있던 건데 어쩌다가 시간 초과가 뜬 코드를 다시 제출했더니 맞다는 결과가 나왔다. (당황스럽네)