[실버 1] 6588. 골드바흐의 추측 (Java)

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

SSAFY10기 동기인 안모군의 조언으로 시간 초과 문제를 해결 할 수 있었습니다. 역시 명예왕~

---

※  문제를 요약하면 아래와 같습니다.

▶ 4보다 큰 모든 짝수는 홀수이면서 소수인 두 수 a, b의 합으로 나타낼 수 있다.

▶ 위 이론은 크리스티안 골드바흐라는 독일의 수학가가 추측한 이론

▶ 백만 이하의 모든 짝수에 대해서 랜덤한 수가 주어질 때, 이 추측을 증명하는 홀수이면서 소수인 두 수 a,b 찾기 

▶ 증명 되는 수 a,b 의 짝이 여러가지 일 경우, b-a의 값이 가장 큰 값으로 출력 

▶ 입력으로 주어지는 수 N은 0이 들어오기 전까지 6이상, 1,000,000 이하의 짝수값으로 주어진다.

▶ 출력은 입력된 수 N 과 골드바흐의 이론을 증명한 두 수 a,b를 활용하여 N = a + b 형태로 출력

▶ 증명하지 못했을 경우 "Goldbach's conjecture is wrong."을 출력

◈ Input

8
20
42
0

◈ Output ( N = a + b 형태 )

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 소수 탐색을 위해 에리스토테네스의 체 구현 (bIsPrime 배열)

▶ 2부터 N까지 본인을 제외한 모든 배수 지우기

▶ 증명 성공, 실패 확인 여부를 위한 bGoldbach 변수 선언

▶ b-a의 가장 큰 차를 찾기 위해 a는 가장 작은 홀수이자 소수인 3 b는 N에서 a를 뺀 N-3으로 초기값 설정

▶ a,b는 반드시 홀수 이므로 각각 +2, -2를 하며 홀수를 유지한 채로 탐색, N=a+b를 만족하며 소수일 경우 탐색 종료

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main{

	public static void main(String[] args) throws IOException  {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		
		int N = Integer.parseInt(bf.readLine());
		
		// 에라토스테네스의 체
		// 1. 2부터 N까지의 모든 자연수를 나열
		// 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
		// 3. 남은 수 중에서 i의 배수를 모두 제거 (i는 keep!)
		// 4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정 반복
		
		boolean[] bIsPrime = new boolean[1000001];
		bIsPrime[1] = true;
		
		for(int i = 2; i <= 1000; i++) {
			if(bIsPrime[i])
				continue;
			
			for(int j = i*i; j <= 1000000; j+=i) {
				if(!bIsPrime[j])
					bIsPrime[j] = true;
			}
		}
		
        	// Goldbach 이론 증명
		while(N != 0) {
			
			boolean bGoldbach = false;
			
			int a = 3;
			int b = N - a;
			while(a <= b) {
				if(!bIsPrime[b] && !bIsPrime[a] &&
						a+b == N) {
					bGoldbach = true;
					bw.write(N + " = " + a + " + " + b + "\n");
					bw.flush();
					break;
				}
				a+=2;
				b-=2;
			}
			
			if(!bGoldbach)
				System.out.println("Goldbach's conjecture is wrong.");
			
			N = Integer.parseInt(bf.readLine());
		}
		
		bw.close();
	}
}

 처음엔 a,b 탐색을 b를 고정 시킨 후, a를 2부터 N까지 완전 탐색하는 방식으로 이중 포문을 돌리니 O(N^2) 형태로 되어 시간초과가 발생하였는데

 SSAFY 동기인 안모군의 투포인터 탐색 조언으로 위와 같이 코드를 변경하여 O(N+N)형태로 시간복잡도 구현을 완료하였습니다. SSAFY10기 만세~

읽어주셔서 감사합니다!

Good Luck! (피드백 고맙습니다)