알고리즘/기초수학
[java 백준] 실버 1/ 6588번 골드바흐의 추측
Meaning_
2021. 9. 19. 10:52
728x90
반응형
https://www.acmicpc.net/problem/6588
6588번: 골드바흐의 추측
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
// 에라토스테네스의 체 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
boolean[] arr = new boolean[1000001];
Stack<Integer> stack = new Stack<>();
for (int i = 2; i < arr.length; i++) {
arr[i] = true;
}
for (int i = 2; i < arr.length; i++) {
if (arr[i] == false) {
continue;
}
for (int j = i + i; j < arr.length; j += i) {
arr[j] = false;
}
}
while (true) {
int n = Integer.parseInt(br.readLine());
boolean havePrime = false;
if (n == 0) {
break;
}
for (int i = 2; i <= n; i++) {
if (arr[i] && arr[n - i]) {
sb.append(n + " = " + i + " + " +(n - i) ).append("\n");
havePrime = true;
break;
}
}
if (havePrime == false) {
sb.append("Goldbach's conjecture is wrong.").append("\n");
}
}
System.out.println(sb.toString());
}
}
|
cs |
에라토스테네스의 체를 먼저 만들어놓고, 2부터 n까지 반복문을 돌려서 가장 먼저 arr[i]값이 true가 나온애(어차피 얘가 b-a값이 가장 큼 , a가 가장 작은 수이기 때문에)를 print해주면된다.
에라토스테네스의 체 알고리즘은
https://we1cometomeanings.tistory.com/145
[java 백준] 실버 2/1929번 소수 구하기
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.a..
we1cometomeanings.tistory.com
여기에 더 자세히 설명해두었다.
문제를 풀면서 틀린부분
|
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
53
54
55
56
57
58
59
60
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
// 에라토스테네스의 체 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean[] arr = new boolean[1000001];
Stack<Integer> stack = new Stack<>();
for (int i = 2; i < arr.length; i++) {
arr[i] = true;
}
for (int i = 2; i < arr.length; i++) {
if (arr[i] == false) {
continue;
}
for (int j = i + i; j < arr.length; j += i) {
arr[j] = false;
}
}
while (true) {
int n = Integer.parseInt(br.readLine());
if (n == 0) {
break;
}
for (int i = 2; i <= n; i++) {
if (arr[i] != false) {
stack.add(i);
}
}
boolean havePrime = false;
while (!stack.isEmpty()) {
int key = stack.peek();
if (stack.contains(n - key)) {
int value = n - key;
System.out.println(n + " = " + key + " + " + value);
havePrime = true;
break;
}
else {
stack.pop();
}
}
if (stack.isEmpty() && havePrime == false) {
System.out.println("Goldbach's conjecture is wrong.");
}
}
}
}
|
cs |
처음엔 스택으로 구현했는데, 이거 때문인지 시간초과가 떴다. 분명 스택의 시간복잡도는 O(1)로 알고 있는데, 왜 시간초가가 뜬지 모르겠다.. 왜 시간초과가 나는지 알고계신분이 있으시다면 댓글 남겨주신다면 정말 감사하겠습니다 ㅜㅜ
728x90
반응형