BOJ-3671 산업 스파이의 편지
9542 단어 bruteforcealgorithmbojalgorithm
필요한 지식
- 완전탐색
- 에라스토테네스의 채
- SET
접근
- 종이 조각으로 만들수 있는 모든 수를 체크해 준다.
- 만든수가 소수라면
SET
에 넣어준다. - 소수 체크에는 에라스토테네스의 채를 사용했다.
코드(C++)
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false), cin.tie(),cout.tie();
using namespace std;
int t;
bool sosu[10000000], chk[8];
string s;
set<int> se;
void init() {
sosu[0] = sosu[1] = true;
for (int i = 2; i * i <= 10000000; i++) {
if (sosu[i]) continue;
for (int j = i + i; j <= 10000000; j += i) {
sosu[j] = true;
}
}
}
void go(int idx,int res) {
if (idx == s.length()) return;
for (int i = 0; i < s.length(); i++) {
if (chk[i]) continue;
chk[i] = true;
if (!sosu[res*10+s[i]-'0'])se.insert(res*10+s[i]-'0');
go(idx + 1,res*10+s[i]-'0');
chk[i] = false;
}
return;
}
int main() {
FIO;
init();
cin >> t;
while (t--) {
memset(chk, 0, sizeof(chk));
cin >> s;
go(0,0);
cout << se.size() << "\n";
se.clear();
}
return 0;
}
결과
Author And Source
이 문제에 관하여(BOJ-3671 산업 스파이의 편지), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hschoi1104/BOJ-3671-산업-스파이의-편지저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)