(출처) https://www.acmicpc.net/problem/2023
소수 판별
처음 문제를 보았을 때 N이 8로 주어지면 10000000 ~ 99999999 까지의 수들 중에서 소수를 걸러내야 하는데 과연 이걸 제한 시간 안에 계산을 수행할 수 있을지에 대한 고민이 컸다.
천만 이상의 수는 소수판별에만 3000번 이상의 계산 반복이 소모되고 구천만 정도의 수를 소수판별하기 위해서는 대략 1만 번의 for문 반복을 돌려야 한다.
(N이 소수인지 아닌지 판별하기 위해서 N의 제곱근 까지의 수들을 모두 나눠보는 식으로 구현한 소수판별 알고리즘을 썼다고 가정했을 때)
만약 정말 무식하게 해당 범위에 존재하는 모든 수에 대하여 소수판별을 진행하는 식으로 구현을 하고자 한다면 당연히 시간초과가 날 것은 뻔했다.
문제에서 주어진 조건
하지만 해당 문제는 단순히 N 자리의 소수를 찾아내기만 하면 되는 것이 아니다.
문제에서 주어진 조건에 의하면 N이 8이라고 했을 때 왼쪽에서 1번째, 2번째, ... , 그리고 8번째까지 자리를 나눠서 구별했을 때 모든 상황에서 소수를 만족하는 수를 찾으라는 조건이 따른다.
지금까지 알고리즘 문제를 여러 번 풀어봤을 때의 경험상, 이러한 제약조건은 문제를 더 어렵게 한다기보다는 의외로 시간을 절약시킬 수 있게 하는 힌트가 되는 경우가 많았다.
해당 문제도 주어진 제약조건으로 인해 오히려 전체 경우의 수를 가지치기 할 수 있게 되어 문제가 더욱 간단해지게 되는 것을 볼 수 있었다.
예를 들자면 N == 1일 때 리턴해야 될 정답은 2, 3, 5, 7이 된다.
이때 문제의 제약조건을 한번 떠올려보면 N == 2 일 때 2, 3, 5, 7을 제외한 다른 수가 1번째 자리에 들어오는 경우가 있을 수 없다는 사실을 발견할 수 있다.
(11의 경우 2자리 수의 소수는 맞지만 왼쪽에서 첫 번째 수가 1로 소수가 아니므로 정답리스트에서 탈락된다)
즉 문제에서 요구하는 N에 대한 정답리스트는, 그 이전 단계 N - 1에서 만든 정답리스트에서 추가적으로 가지를 이어주는 식으로 진행된다.
따라서 나는 주어진 N에 대한 모든 범위의 수를 소수판별할 필요 없이, 그 이전 단계에서 만든 수들을 추가적으로 이용하여 현 단계에 존재하는 소수 리스트가 어떻게 되는지 확인해 주면 된다.
구현
{2, 3, 5 ,7 } 중 첫 시작은 2 에서 부터 시작한다.
다음 자리수에 들어올 수 있는 수가 무엇이 되는 지 1 ~ 9 까지 모든 경우를 대입해 보면서 확인해 본다.
(즉 21, 22, 23 ... 29를 모두 확인해보며 소수인 수가 있는 지 확인해 본다는 것)
만약 소수인 수를 찾게되었다면 다음 3번째 자리 수를 찾기 위해 위의 행위를 재귀적으로 반복한다.
즉 이 같은 행위를 주어진 자리수 N을 모두 만족할 때 까지 재귀적으로 파고 들어가며 반복하면 된다.
2에 대한 모든 정답리스트를 찾는 작업을 완료했다면 3, 5 ,7 에 대해서도 똑같이 반복해주면 된다.
시간복잡도
N == 8일 때 마지막 단계의 작업을 한번 떠올려보면, N == 7일 때의 정답리스트들에 모두 1 ~ 9 까지 수를 추가해보며 소수판별을 진행하게 된다.
이때 소수판별에 소모되는 계산 연산을 넉넉잡아 대략 1만 번의 반복을 진행한다고 가정한다면,
(N == 7일때의 정답들 * 10 * 1만) 정도의 계산이 필요하다.
만약 N == 7일때 정답리스트에 포함되는 원소가 대략 1000개 정도라고 가정한다면 약 1억번의 계산 연산이 되는데 1억 정도라면 주어진 시간제한 안에 충분히 계산할 수 있는 양이라고 볼 수 있다.
그런데 예제에서 주어진 N == 4일 때의 정답리스트 아웃풋을 보면 원소의 개수가 20개도 안된다.
이후 N == 5일 때, 6일 때 원소의 개수가 늘어날 수도 줄어들 수도 있겠지만 문제의 제약조건이 워낙 까다롭기 때문에 아무리 늘어난다고 하더라도 N == 7일 때 정답리스트의 원소개수가 1000개까지 늘어날 가능성은 매우 적어 보였다.
따라서 해당 로직이라면 충분히 문제를 해결할 수 있어 보였다.
코드
#pragma warning (disable : 4996)
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
vector<int> ret;
int N;
bool is_prime(int n) {
int root_n = (int) floor(sqrt(n));
for (int i = 2; i <= root_n; i++) {
if (n % i == 0) return false;
}
return true;
}
void recul(int level, int num) {
if (level == N) {
ret.push_back(num);
return;
}
for (int i = 1; i <= 9; i++) {
if (is_prime(num * 10 + i)) {
recul(level + 1, num * 10 + i);
}
}
return;
}
int main() {
cin >> N;
if (N == 1) {
cout << "2\n3\n5\n7\n";
return 0;
}
ret = vector<int>();
recul(1, 2);
recul(1, 3);
recul(1, 5);
recul(1, 7);
sort(ret.begin(), ret.end());
for (int i = 0; i < ret.size(); i++) cout << ret[i] << "\n";
return 0;
}기억하고 싶은 점
위 로직으로 문제의 정답을 띄우긴 했지만 시간복잡도를 계산할 때, N == 7일 때 원소의 개수가 1000개 이하로 떨어질 것이라는 완벽한 증명은 하지 못했다.
감에 의존하면 원소의 개수가 무조건 1000개 이하가 될 것 같긴 한데 그렇다고 정확한 수학적 증명을 이끌어내서 해결한 것은 아니었다.
조금 더 엄밀한 증명으로 문제를 해결할 수 있었으면 좋겠는데, 내가 가진 수학적 지식이 워낙 짧아서 이걸 제대로 증명할 수 있는 것인지 뭔가 느낌조차 오지 않는다.
그래서 우선은 여기까지 하고 넘어가기로 했다.
또한 소수판별을 위한 알고리즘은 오래돼서 기억이 가물가물 했었는데 오랜만에 다시 한번 생각해 볼 수 있게 해준 좋은 문제였던 것 같다.
