2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
메모리 제한이 4MB이라서 에라토스테네스의 체를 사용할 수 없습니다.
그래서 소수인지 판별하는 부분을 2부터 반복문을 돌리는 방법을 선택해서 시간초과가 뜰것 같았지만 다행히도 AC를 받았습니다.
우선 문제의 7331을 보면 7331도 소수, 733도 소수, 73도 소수, 7도 소수입니다.
즉 일의자리부터 숫자 하나씩 뺀 부분 숫자도 소수여야합니다.
저는 백트래킹으로 맨 앞의 자리부터 구하였습니다.
우선 맨 앞의 자리에 올 수 있는 숫자는 2, 3, 5, 7입니다. (일의자리 소수)
각 숫자가 맨 앞의 올 경우를 구하기 위해 4번의 dfs를 돌립니다.
dfs에서는 일의자리로 올 숫자를 구하는것이기 때문에 짝수가 올 수 없으므로 홀수만 돌려줍니다.
next가 소수이면 재귀를 돌려주었고, 뽑은 숫자가 N개가 되면 지금까지 뽑은 숫자를 출력합니다.
[C++]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
using namespace std;
int N;
bool prime(int x) {
for (int i = 2; i*i <= x; i++) {
if (!(x % i)) return false;
}
return true;
}
void dfs(int cnt, int x) {
if (cnt == N) {
cout << x << '\n';
return;
}
for (int i = 1; i <= 9; i += 2) {
int next = x * 10 + i;
if (!prime(next)) continue;
dfs(cnt + 1, next);
}
}
void func() {
dfs(1, 2);
dfs(1, 3);
dfs(1, 5);
dfs(1, 7);
}
void input() {
cin >> N;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[Java]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int N;
static boolean primeCheck(int x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0)
return false;
}
return true;
}
static void dfs(int cnt, int x) {
if (cnt == N) {
sb.append(x).append("\n");
return;
}
for (int i = 1; i <= 9; i += 2) {
int next = x * 10 + i;
if (!primeCheck(next))
continue;
dfs(cnt + 1, next);
}
}
static void func() {
dfs(1, 2);
dfs(1, 3);
dfs(1, 5);
dfs(1, 7);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws Exception {
input();
func();
System.out.print(sb.toString());
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 2458 키 순서 (0) | 2021.04.13 |
|---|---|
| boj 14889 스타트와 링크 (0) | 2021.03.17 |
| boj 14500 테트로미노 (0) | 2021.03.15 |
| boj 16922 로마 숫자 만들기 (0) | 2021.02.24 |
| boj 1987 알파벳 (0) | 2021.02.18 |