[백준 9020] 골드바흐의 추측

[문제 바로가기]👇

9020번: 골드바흐의 추측

 

 

💡풀이💡

가장 먼저 2부터 n까지 숫자 중에 소수를 찾아서 그 소수의 합이 n이 되는 수들을 찾아야 했다.

최댓값인 10000까지 수들이 소수인지 아닌지를 저장해 두 수를 더했을 때 

더해지는 두 수가 소수인지 아닌지 O(1)에 찾는 방법으로 접근했다.

 

 

1. 2 ~ 10000까지 모든 소수 구하기

최대 입력 값이 10000이기 때문에 10000까지의 수가 소수인지 아닌지를 boolean형 배열로 저장해도 충분하다!

10000또한 포함해줘야 하기 때문에 총 10001개의 배열을 생성했고 에라토스테네스의 채 알고리즘을 사용해

각 숫자가 소수인지(true) 아닌지(false)를 배열에 저장했다.

// 2 ~ 10000까지 모든 소수 구하기
boolean[] isPrime = new boolean[10001];

// 초기값은 모두 true
for(int i=2; i<isPrime.length; i++) {
	isPrime[i] = true;
}

// 에라토스테네스의 채
for(int i=2; i<=Math.sqrt(10000); i++) {
	for(int j=i*i; j<=10000; j+=i) {
		isPrime[j] = false; // 소수 아닌 수들 체크
	}
}

 

 

2. 골드바흐 파티션 구하기

문제 답인 골드바흐 파티션을 찾으려면 두 가지 조건이 있다.

골드바흐 파티션은 1) 두 소수의 합으로 이뤄져있고, 골드바흐 파티션이 여러 개일 경우

2) 두 소수의 차이가 가장 작은 것을 찾아야 한다.

 

두 소수의 차이가 가장 작다는 것은 두 수가 n의 절반(n/2)에 가깝다는 뜻이기 때문에 

n/2를 시작점으로 잡고 여기서부터 골드바흐 파티션을 찾아갔다

mid  :: n의 절반
num-mid :: mid와 더했을 때 n이 되는 수

으로 두고

 

두 수가 모두 소수일때 조건 1) , 2)번을 모두 만족하는 골드바흐 파티션이 되기 때문에 바로 출력한다.

아니면 mid를 감소하는데 그러면 자연스럽게 num-min는 증가하게 된다.

 

이 과정을 반복한다.

for(int t=0; t<T; t++) {
	int num = Integer.parseInt(br.readLine());
			
	int mid = num/2;  
	while(true) {
		if(isPrime[mid] && isPrime[num-mid]) { 
			sb.append(mid).append(" ").append(num-mid).append("\n");
			break;
		}
		mid--;
	}			
}

 

전체 코드

package M04_5;

import java.io.*;

public class B9020 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		// 2 ~ 10000까지 모든 소수 구하기
		boolean[] isPrime = new boolean[10001];
		for(int i=2; i<isPrime.length; i++) {
			isPrime[i] = true;
		}
		for(int i=2; i<=Math.sqrt(10000); i++) {
			for(int j=i*i; j<=10000; j+=i) {
				isPrime[j] = false;
			}
		}
		
		for(int t=0; t<T; t++) {
			int num = Integer.parseInt(br.readLine());
			
			int mid = num/2;  
			while(true) {
				if(isPrime[mid] && isPrime[num-mid]) {
					sb.append(mid).append(" ").append(num-mid).append("\n");
					break;
				}
				mid--;
			}			
		}
		System.out.println(sb);
		br.close();
	}
}