[JAVA] 백준 9020번 : 골드바흐의 추측
https://www.acmicpc.net/problem/9020
9020번: 골드바흐의 추측
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아
www.acmicpc.net
ㅇ 문제
입력한 수를 만족하는 소수의 합을 구하는 문제이다.
소수를 찾아야 하니 에라토스테네스의 체를 이용해여 접근한다.
◆ 핵심 아이디어
1. 입력값까지의 소수를 구해야 한다.
2. 입력값의 소수의 합을 출력한다.
3. 소수의 합(골드바흐 파티션)이 여러 개일 경우, 두 소수의 차이가 가장 적은 것을 출력한다.
4. 소수는 작은 것부터 출력한다.
◆ 에라토스테네스의 체
[Algorithm] JAVA 소수판별 - 에라토스테네스의 체
ㅇ 소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다. ㅇ 소수 찾기 소수를 찾는 방법은 총 3가지가 있다. 1. N을 N보다 작은 자연수로
sfida.tistory.com
ㅇ 천천히 접근하기
1. 소수 찾기
먼저 에라토스테네스의 체 알고리즘을 이용하여 10000까지 소수를 찾을 것이다. 0부터 10000까지의 길이를 가져야 하니 prime 배열의 크기는 10001이다.
isPrirme의 경우, 에라토스테네스의 체 알고리즘이다. 위 링크의 에라토스테네스의 체 알고리즘을 숙지한 후, 코드를 읽으면 이해가 쉬울 것이다.
class Main {
public static boolean[] prime = new boolean[10001];
static void isPrime() {
prime[0] = true;
prime[1] = true;
for(int i=2; i<Math.sqrt(prime.length); i++) {
if(prime[i]) continue;
for(int j=i*i; j<prime.length; j+=i) {
prime[j] = true;
}
}
}
}
2. 입력받기
테스트케이스 T를 입력하고, T의 개수만큼 숫자를 입력하도록 하였다.
import java.io.*;
class Main {
public static boolean[] prime = new boolean[10001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
int num = Integer.parseInt(br.readLine());
}
}
static void isPrime() {
prime[0] = true;
prime[1] = true;
for(int i=2; i<Math.sqrt(prime.length); i++) {
if(prime[i]) continue;
for(int j=i*i; j<prime.length; j+=i) {
prime[j] = true;
}
}
}
}
3. 골드바흐 파티션 구하기 (짝수 num에 대한 소수의 합)
먼저 isPrime()을 실행시킨 후, 소수를 판별한다.
res1과 res2는 최종 출력할 값이 할당되며, min과 abs는 소수의 값이 적은 것을 찾기 위해 할당되었다.
if(prime[j] || prime[num-j]) continue;
> j와 num-j의 합은 num이다. 우리는 소수의 합이 num인 것을 찾아야 한다.
> j와 num-j는 하나라도 true가 나오면 안된다. false인 소수를 찾아야 하기 때문에 || 연산자를 넣어주었다.
> continue로 인해 그 후의 코드는 j와 num-j가 소수인 것들만 남는다.
if(min>abs) {
res1 = j;
res2 = num-j;
min = abs;
}
> 두 소수의 차의 절댓값이 min보다 작으면 최종 출력할 값은 j와 num-j가 되고 min은 abs로 변경된다.
> 이 과정을 통해 두 수의 차가 적은 것이 남게 된다.
import java.io.*;
import java.util.*;
class Main {
public static boolean[] prime = new boolean[10001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 소수 판별
isPrime();
int a = Integer.parseInt(br.readLine());
for(int i=0; i<a; i++) {
int num = Integer.parseInt(br.readLine());
// 출력할 최종 골드바흐 파티션
int res1 = 0, res2 = 0;
// 골드바흐 파티션이 여러 개일 경우, 작은 것부터 출력하기 위한 변수 할당
int min = 10000, abs = 0;
// 2부터 1씩 증가하면서 소수의 합 탐색
for(int j=2; j<num; j++) {
// prime[j] 와 prime[num-j]가 하나라도 true(소수가 아닌 수)가 있으면 안되므로
// 뒤의 코드는 무시한다.
if(prime[j] || prime[num-j]) continue;
// 여기엔 소수만 남게 된다.
// 두 소수의 차의 절댓값을 찾는다.
abs = Math.abs(num-j-j);
if(min>abs) {
res1 = j;
res2 = num-j;
min = abs;
}
}
System.out.println(res1 + " " + res2);
}
}
static void isPrime() {
prime[0] = prime[1] = true;
for(int i=2; i<Math.sqrt(prime.length); i++) {
if(prime[i]) continue;
for(int j=i*i; j<prime.length; j+=i) {
prime[j] = true;
}
}
}
}
ㅇ 최종 코드
import java.io.*;
import java.util.*;
class Main {
public static boolean[] prime = new boolean[10001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
isPrime();
int a = Integer.parseInt(br.readLine());
for(int i=0; i<a; i++) {
int num = Integer.parseInt(br.readLine());
int res1 = 0;
int res2 = 0;
int min = 10000, abs = 0;
for(int j=2; j<num; j++) {
if(prime[j] || prime[num-j]) continue;
abs = Math.abs(num-j-j);
if(min>abs) {
res1 = j;
res2 = num-j;
min = abs;
}
}
System.out.println(res1 + " " + res2);
}
}
static void isPrime() {
prime[0] = prime[1] = true;
for(int i=2; i<Math.sqrt(prime.length); i++) {
if(prime[i]) continue;
for(int j=i*i; j<prime.length; j+=i) {
prime[j] = true;
}
}
}
}
ㅇ 배운점
에라토스테네스의 체를 공부하면서 블로그에 정리한 적이 있다. 확실히 직접 기록하면서 습득하니 훨씬 기억에 오래 남았다. 이 글을 보고 공부한다면 직접 생각하고, 기록하면서 공부하는 것을 추천한다.
에라토스테네스의 다양한 유형을 풀어보면서 더 확실히 익혀야겠다.