문제 이해 단계
문제 자체는 굉장히 심플하다.
0 ~ 9까지 숫자를 딱 한 번씩만 사용해서 K자릿수를 만드는데
아래의 두 조건을 동시에 만족하는 수가 몇 개인지 구하는 문제
1. 서로 다른 소수의 합으로 나타낼 수 있어야 함
2. M으로 나누어 떨어지지 않을 때까지 나눈다. (계속 나눈다.)
더 이상 나눌 수 없을 때의 수는 소수의 곱이다. ( 이때의 두 소수는 같아도 됨)
문제 접근 단계
일단 문제 조건에서 공통적으로 소수라는 키워드가 계속 나온다.
소수의 합이던 소수의 곱이던
알기 위해선 일단 소수를 알아야 한다.
이럴 때 쓰이는 대표적인 수학적 알고리즘은
에라토스테네스의 체이다.
이를 이용하여 K = 5 일 때 즉 5자리일 때
(99999)까지 일 때의 소수를 모두 구할 수 있다.
소수의 리스트들을 모두 구했기 때문에
이들을 조합하면 소수의 합과 곱을 모두 구할 수 있다.
이제 이를 이용해서 조건 1,2를 만들어보면 된다.
1. 서로 다른 소수의 합
모든 소수 리스트들에 대해 이중반복으로 일일이 비교하는 것은
엄청난 부담으로 나름의 최적화를 해줘야 한다.
그래서 중복계산을 되도록 줄이고,
소수 리스트는 오름차순으로 배열되어 있기 때문에
(에라토스테네스의 체 밑에서 설명)
소수의 값이 나올 수 있는 자릿수 K를 넘으면
그 반복문을 탈출하도록 해두었다.
또한 서로 다른 두 소수이기 같은 소수일 경우는 제외하였다.
이는 밑에서 코드로 함께 보겠다.
어쨌든 이런 식으로 서로 다른 소수의 합을 모두 담아두었다.
2. 소수의 곱
소수의 곱 같은 경우에는 같은 소수도 곱할 수 있기 때문에
이중 반복문을 돌릴 때 중복 계산만 안 해주도록 주의해 주면 된다.
한 가지 주의해야 할 점은 K가 최대 10^5자리,
즉 10^5x 10^5 = 10^10 이므로 int의 범위를 넘는다.
즉 연산하는 과정에서 오버플로우를 피하기 위해
long으로 자료형을 받아야 한다는 것이다.
이렇게 소수의 곱의 리스트를 구해주면 된다.
3. 중복되지 않는 K자리 수 만들기
결국에는 특정 수가 위의 두 리스트에
동시에 들어있는지를 확인하는 것이다.
그 특정수는 K자리 수이고 각 자릿수가 중복되지 않는다.
이를 구현하기 위해 약간의 백트래킹 같은 재귀함수를 사용했다.
0부터 시작해서 9까지 반복하는 반복문에서
자릿수를 뒤로 옮기면서 다시 0~9를 호출하는데,
이미 호출했던 것은 나오지 않게 하면서 중복을 방지한다.
재귀함수를 반복하다가 K자릿수가 되면
합과 곱 리스트에 동시에 속해 있는지를 확인한다.
이 과정을 계속 반복한다. 이것도 그냥 코드로 다 같이 보자.
해당 문제의 로직은 그렇게 어려운 편이 아니지만
10^9까지의 소수를 통해 곱과 합을 구하고 또다시 수를 비교해야 한다.
그래서 비교하는 로직을 얼마나 최적화하고
코드를 시간적으로 최적화하는지가 관건인 문제이다.
문제 구현 단계
// 나올 수 있는 소수 다 찾기(에라토스테네스의 체)
vector<int> getPrime(int length){
bool prime[length]; // length 길이만큼 배열 생성
vector<int> list; // 최종적으로 반환할 vector
list.reserve(length); // 미리 length만큼의 공간 할당
for(int i = 2; i <= length; i++) prime[i] = true; // 기본 true
for(int i = 2; i*i <= length; i++){
if(prime[i]){
// i가 소수면 i이후의 i 배수는 소수가 아님(약수로 i로 가짐)
// i * k (k < i)까지 이미 검사됐으므로 j 시작 값을 i*2에서 i*i로 개선 가능
for(int j = i * i; j <= length; j += i) prime[j] = false;
}
// prime[i]가 false면 i와 i 배수는 어차피 소수가 아님(검사할 필요 없음)
}
// true(소수) 값을 list에 담음
for(int i = 2; i <= length; i++) if(prime[i]) list.push_back(i);
return list;
}에라토스테네스의 체를 구현함 함수이다.
반환값으로 vector <int>로 소수 리스트를 담아 반환하다.
매개변수로는 최대 크기가 들어간다.(K에 따라 바뀜)
여기서 list에 reserve를 사용하여
length만 길이를 미리 할당해 준 이유는
push_back의 시간을 줄이기 위해서이다.
벡터에 공간을 할당해주지 않은 채 push_back을 하면
생성을 한 후 push_back을 하기 때문에 시간이 훨씬 더 오래 걸린다.
그래서 배열의 크기를 알고 있다면 reserve로 미리 생성을 해두고
push_back으로 넣으면 시간을 훨씬 절약할 수 있다.
소수 체크는 bool형 배열로 시작했는데,
일단 모두 소수(true)로 보고 시작한다.
그리고 i = 2부터 시작하여 2를 소수로 보고
그 배수들은 모두 false로 처리해 준다.
그리고 시간을 줄이기 위해 j의 시작점을 i*i로 잡는다.
연산이 끝난 후 소수인 것(true)인 것만 list에 담아 반환한다.
// 서로 다른 소수의 합
vector<bool> getSum(vector<int> prime,int length){
vector<bool> list;
list.resize(length,false);
for(int i = 0; i < prime.size(); i++){
// 최대 크기를 넘어가면 반복문 탈출
if(prime[i] >= length) break;
for(int j = 0; j < prime.size(); j++){
if(i == j) continue; // 두 소수가 같은 경우 제외
int val = prime[i] + prime[j];
// 최대 크기보다 작은 경우만
if(val < length) list[val] = true;
}
}
return list;
}서로 다른 소수의 합을 구하는 getSum함수이다.
매개변수로 아까 구했던
소수의 리스트 prime 벡터와 최대 크기가 들어간다.
반환값으로는 bool값이 들어간다.
이것도 마찬가지로 시간을 줄이기 위해서 resize를 활용해서
length만큼의 크기를 할당해 주고 false로 미리 초기화해 놨다.
나머지는 이중반복문으로 탐색하면서
두 소수가 같은 경우와 length보다 클 때를 제외하고선
그 값을 true로 바꾼다.
여기서 list [val] = true는 숫자 val은 소수라는 뜻이다.
vector<bool> getMultiple(vector<int> prime,int length){
vector<bool> list;
list.resize(length,false);
for(int i = 0; i < prime.size(); i++){
if(prime[i] >= length) break;
for(int j = 0; j < prime.size(); j++){
long val = (long)prime[i] * (long)prime[j];
if(val < length) list[val] = true;
}
}
return list;
}
비슷한 로직인 두 소수의 곱셉을 구하는 함수이다.
아까 말했듯 두 곱셈을 long 자료형으로 변환하여
오버플로우가 발생하지 않도록 한다.
// 해당 숫자가 소수인지 판단
bool isPossible(int num, vector<bool> addList, vector<bool> mulList){
if(!addList[num]) return false;
// 나눠지지 않을때까지 나눔
while(num % M == 0) num /= M;
if(!mulList[num]) return false;
return true;
}
// 중복되지 않는 K자리 수 만들기
void findCommon(int idx, int cnt,vector<bool> addList, vector<bool> mulList){
// K자리 수가 다 만들면 소수인지 확인
if(idx == 0){
if(isPossible(cnt,addList,mulList)){
ans++;
}
return;
}
// 0 ~ 9까지 한번씩 호출
for(int i = 0; i <= 9; i++){
// 맨 앞자리 0이 들어오는 거 방지
if((i == 0 && idx == K) || v[i]) continue;
// 방문 체크로 중복 방지
v[i] = true;
findCommon(idx-1,cnt*10+i,addList,mulList);
v[i] = false;
}
}
isPossible은 매개변수로 들어온
num이 소수인지 판단하는 함수이다.
그냥 두 소수의 합 리스트와,
곱 리스트에 동시에 들어있는지 확인하는 것
아래의 findCommon은 중복되지 않는 K자릿수를 만드는 함수이다.
idx는 숫자 자리를 의미하는 것이고 idx = 0이라는 것은
K 자릿수가 완성됐다는 것을 의미하므로 isPossible을 호출한다.
그 아래에 반복문은 0 ~ 9 까지를 반복 하며
재귀함수를 통해 숫자를 만든다.
v [i]는 방문을 확인하는 배열이다.
이 배열을 통해 이미 사용했던 숫자는 사용하지 않도록 한다.
중요한 것은 재귀가 끝날 때 방문을 해제해 줌으로써
다시 사용가능하도록 해줘야 한다는 것이다.
여기까지가 설명의 끝이고
이제 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
#define MAXSIZE 99999
int ans = 0;
int K, M;
bool v[10] = {false};
// 나올 수 있는 소수 다 찾기(에라토스테네스의 체)
vector<int> getPrime(int length){
bool prime[length]; // length 길이만큼 배열 생성
vector<int> list; // 최종적으로 반환할 vector
list.reserve(length); // 미리 length만큼의 공간 할당
for(int i = 2; i <= length; i++) prime[i] = true; // 기본 true
for(int i = 2; i*i <= length; i++){
if(prime[i]){
// i가 소수면 i이후의 i 배수는 소수가 아님(약수로 i로 가짐)
// i * k (k < i)까지 이미 검사됐으므로 j 시작 값을 i*2에서 i*i로 개선 가능
for(int j = i * i; j <= length; j += i) prime[j] = false;
}
// prime[i]가 false면 i와 i 배수는 어차피 소수가 아님(검사할 필요 없음)
}
// true(소수) 값을 list에 담음
for(int i = 2; i <= length; i++) if(prime[i]) list.push_back(i);
return list;
}
// 서로 다른 소수의 합
vector<bool> getSum(vector<int> prime,int length){
vector<bool> list;
list.resize(length,false);
for(int i = 0; i < prime.size(); i++){
// 최대 크기를 넘어가면 반복문 탈출
if(prime[i] >= length) break;
for(int j = 0; j < prime.size(); j++){
if(i == j) continue; // 두 소수가 같은 경우 제외
int val = prime[i] + prime[j];
// 최대 크기보다 작은 경우만
if(val < length) list[val] = true;
}
}
return list;
}
vector<bool> getMultiple(vector<int> prime,int length){
vector<bool> list;
list.resize(length,false);
for(int i = 0; i < prime.size(); i++){
if(prime[i] >= length) break;
for(int j = 0; j < prime.size(); j++){
long val = (long)prime[i] * (long)prime[j];
if(val < length) list[val] = true;
}
}
return list;
}
// 해당 숫자가 소수인지 판단
bool isPossible(int num, vector<bool> addList, vector<bool> mulList){
if(!addList[num]) return false;
// 나눠지지 않을때까지 나눔
while(num % M == 0) num /= M;
if(!mulList[num]) return false;
return true;
}
// 중복되지 않는 K자리 수 만들기
void findCommon(int idx, int cnt,vector<bool> addList, vector<bool> mulList){
// K자리 수가 다 만들면 소수인지 확인
if(idx == 0){
if(isPossible(cnt,addList,mulList)){
ans++;
}
return;
}
// 0 ~ 9까지 한번씩 호출
for(int i = 0; i <= 9; i++){
// 맨 앞자리 0이 들어오는 거 방지
if((i == 0 && idx == K) || v[i]) continue;
// 방문 체크로 중복 방지
v[i] = true;
findCommon(idx-1,cnt*10+i,addList,mulList);
v[i] = false;
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> K >> M;
int length = pow(10,K);
vector<int> prime = getPrime(length);
vector<bool> addList = getSum(prime,length);
vector<bool> mulList = getMultiple(prime,length);
findCommon(K,0,addList,mulList);
cout << ans;
}
시행착오
정말 힘들게 힘들게 풀었던 것 같다.
시간초과를 벗어나기가 너무 힘들었다.
인터넷에 C++로 된 풀이도 없어서
다른 언어로 된 풀이를 참고했는데도 시간초과가 떠서
어쩌나 저쩌나 하고 있었는데 reserve를 통해 다행히 해결하였다.
그래도 이 문제 덕분에 reserve를 통한
시간 절약법을 알아가는 것 같아서 다행이다.
구현 문제 어렵다.