문제 설명
- 한개의 숫자(0-9)가 적혀있는 카드로 구성된 덱이 있다.
- 이 덱을 조합하여 소수를 만들 수 있는 개수는?
<힌트>
1. 덱을 조합할 때 어떤 순서로 몇 개를 이어붙일지는 자유로움
2. 소수에는 0과 1이 포함되지 않음
3. 01과 1은 같은 숫자임
4. 덱의 길이는 7이하이다.
아이디어
덱의 길이가 7이하이므로 가장 큰 인풋에 대해 7!개의 소수 후보가 생성된다. 한번 생성된 가장 큰 소수 후보는 9999999의 값을 가질 수 있다.
고로 나눗셈을 제일 많이 하는 테케의 경우
7! 9999999 = O( n (10^(n+1)-1))
번의 나눗셈을 할 것이다.
7!이 7200보다 작아서 완전탐색은 할만한데
각 케이스가 소수인지 어떻게 판별할 것인가? 라는 의문이 들었다.
"9999999"로 구성된 덱의 경우 탐색 1회당 9999998(항상 그런 건 아니지만)번의 나눗셈을 한다는 게 에바쎄바인 것 같았다...
그래서 에라스토테네스의 체와 메모이제이션을 이용해 9999999까지의 숫자들의 소수 여부를 저장하는 테이블을 만들려고 했는데
메모리를 100mb == 10^(8)byte 정도 잡아먹길래 걍 하나씩 검사하게 되었다.
다시 푼 풀이
레벨2 실력체크에서 이 문제가 2번문제로 출제되어 다시 풀어봤다.
dfs가 깔끔해졌다.
#include <string>
#include <vector>
#include<math.h>
#include<iostream>
#include<set>
using namespace std;
//소수인지 판단할 수 있는 함수
bool is_sosu(int n){
if(n==1||n==0){
return false;
}
if(n == 2){
return true;
}
for(int i = 2;i<=sqrt(n);i++){
if(n%i==0){
return false;
}
}
return true;
}
void dfs(string &numbers,int idx,int sz,set<int> &s){
if(idx == sz){
//소수인지 검사
string ns = numbers.substr(0,sz);
int n = stoi(ns);
//cout<<"idx == size() "<<n;
if(is_sosu(n)){
set<int>::iterator it = s.find(n);
if(it==s.end()){
s.insert(n);
//cout<<"새로운 소수를 넣고 있습니다"<<endl;
}
//cout<<"은 소수입니다."<<endl;
}
return;
}
dfs(numbers, idx+1,sz,s);
for(int i = idx+1;i<numbers.size();i++){
string child = numbers;
//swap
char t = child[idx];
child[idx] = child[i];
child[i] = t;
dfs(child,idx+1,sz,s);
}
}
int solution(string numbers) {
int answer = 0;
set<int> s;
for(int i = 1;i<=numbers.size();i++){//i는 sz
dfs(numbers,0,i,s);
}
answer = s.size();
cout<<s.size()<<endl;
return answer;
}삽질
-
소수의 정의에 0과 1은 제외된다는 걸 까먹었다.
-
4를 소수라고 판별해버린 사건^q^..
소수인지 검사할 때 어차피 대칭이니까 [2, n) 로 다 나누지 않고
[2,n/2) 로 나눴는데어차피 리니어타임인데 그냥 멋내고싶었다...
4일 때 2로 나누는 경우를 패스해버리는 문제가 있었다^^^.. -
완전탐색을 잘 못함
일단 처음에 무적권 카드를 다 써서 소수 후보가 나올 수 있는줄 착각해서
수정하는데 오래 걸렸다.
수정한 결과물을 요약하자면 다음과 같다. -
ㅋㅋㅋㅋㅋ어제 next_permutation()써서 한문제 풀어놓고 왜 오늘은 굳이 dfs를 쓴것일까..... 어제 dfs를 쓰고 오늘 next_permutation()쓰면 더 빨랐을텐데 ㅋ..ㅋ.ㅋ.
//dfs
void dfs(int idx,int sz,string s){//idx번째가 판가름 나야하는 상황
if(idx==sz){
//소수라면 int로 조져
string res = s.substr(0,sz);
int n = atoi(res.c_str());
if(is_sosu(n)){
//소수에 추가
}
return;
}
dfs(idx+1,sz,s);//자신상태에 대해서도
for(int i =idx+1;i<s.size();i++){//idx 뒤에 것들을 idx자리로보내보자
string c = s;
swap_idx(c,idx,i);
dfs(idx+1,sz,c);
}
//main
for(int i = 0;i<numbers.size();i++){
int n = numbers[i]-'0';
if(is_sosu(n)){
}
}
for(int sz = 2;sz<=numbers.size();sz++){
dfs(0,sz,numbers);
}코드
#include <string>
#include <vector>
#include<set>
#include<iostream>
using namespace std;
set<int> sosu_coll;
//에라스토테네스의 체로 소수 채워넣음?<-어차피 완전탐색(7!)개수만큼만 검사하면됨
//일단 하나짜리를 소수인지 검사하자(400mb태이블절약)
bool is_sosu(int n){
if(n==1||n==0){
return false;
}
for(int i =2;i <= n / 2;i++){
if( n % i == 0){
return false;
}
}
return true;
}
void swap_idx(string &s, int idx, int i){
char t = s[idx];
s[idx] = s[i];
s[i] = t;
}
int full_num = 0;
void dfs(int idx,int sz,string s){//idx번째가 판가름 나야하는 상황
if(idx==sz){
//소수라면 int로 조져
string res = s.substr(0,sz);
int n = atoi(res.c_str());
if(is_sosu(n)){
set<int>::iterator it = sosu_coll.find(n);
if(it==sosu_coll.end()){//중복없이 올려주기
sosu_coll.insert(n);
//cout<<"inserting new sosu : "<<n<<endl;
}
}
//cout<<res<<endl;
return;
}
dfs(idx+1,sz,s);//자신상태에 대해서도
for(int i =idx+1;i<s.size();i++){//idx 뒤에 것들을 idx자리로보내보자
string c = s;
swap_idx(c,idx,i);
dfs(idx+1,sz,c);
}
}
int solution(string numbers) {
int answer = 0;
//1사이즈짜리는 따로 검사
//cout<<"4 is sosu"<<is_sosu(4)<<endl;
for(int i = 0;i<numbers.size();i++){
int n = numbers[i]-'0';
if(is_sosu(n)){
set<int>::iterator it = sosu_coll.find(n);
if(it==sosu_coll.end()){//중복없이 올려주기
sosu_coll.insert(n);
//cout<<"inserting new sosu : "<<n<<endl;
}
}
}
for(int sz = 2;sz<=numbers.size();sz++){
dfs(0,sz,numbers);
}
answer = sosu_coll.size();
/*
for(set<int>::iterator it = sosu_coll.begin();it!=sosu_coll.end();it++){
cout<<*it<<" ";
}
cout<<endl;
*/
return answer;
}