[JAVA] 백준 (실버1) 6588번 골드바흐의 추측

링크

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

---

문제 설명

(정답률 22.409%)
1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

• 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

---

입력 예제

8
20
42
0

---

출력 예제

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

---

나의 코드

1. 시간 제한이 0.5초 이므로 반복문은 최대한 지양해야 한다.
2. 입력값이 주어질 때마다 소수를 찾으면 시간 초과가 되므로
3. 우선 입력값의 최대 범위까지의 소수를 찾은 배열을 미리 만들어둔다.
4. a와 b를 각각 찾는 이중for문으로 쓸 경우 시간 초과가 난다.
5. 그래서 변수를 두개를 쓰는게 아니라 a하나만 찾고 하나는 n-a를 쓴다.

import java.io.*;

public class Main {
	//테스트 케이스의 범위가 6 <= n <= 1000000,
    //백만까지 이므로 크기가 1000001인 배열을 static으로 생성
    final static int MAX = 1000000;
    static boolean[] primeNumber = new boolean[MAX + 1];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        int[] result;
        //소수를 찾는 메소드 실행
        findPrimeNumber(primeNumber);

		//num이 0이 나올때까지 반복
        while (num != 0) {  
            result = new int[2];

			//num이하인 경우에 대해 for문으로 반복
            for (int i = num; i >= 0 ; i--) {

				//i와 num-i가 소수일 때 문제에 맞게 출력하고
                //num-i의 차이가 최대여야 하므로 break
                if (primeNumber[i] && primeNumber[num - i]) {
                    result[0] = num - i;
                    result[1] = i;
                    bw.write(num + " = " + result[0] + " + " + result[1] + "\n");
                    break;
                }
            }
			//result의 원소가 0일때는 문제에 해당하는 경우가 없다는 뜻
            if (result[0] == 0)
                bw.write("Goldbach's conjecture is wrong." + "\n");

            num = Integer.parseInt(br.readLine());
        }
        bw.close();
    }
    
    //매개변수로 주어진 배열에서 소수인 원소를 체크하여 반환하는 메소드
    static boolean[] findPrimeNumber(boolean[] arr) {

        int cnt;
        for (int i = 2; i < arr.length; i++) {
            cnt = 0;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    cnt++;
                    break;
                }                               
            }
            if (cnt == 0) {
                arr[i] = true;
            }
        }
        return arr;               
    }
}

---

정리

답을 찾는거 자체는 크게 어렵지 않았으나 이 문제가 정답률이 낮은 이유는
시간 제한이 0.5초이기 때문이다.
처음에는 입력값이 주어질 때마다 입력값 이하의 소수를 구해서 List에 넣고
이중 for문을 구성해 a와 b를 따로 구했었다.
이렇게 하니 반복문이 너무 많아져서 계속 시간초과가 났다.
그래서 질문 게시판을 참고하다가 소수에 대한 배열을 미리 생성하라길래
미리 입력 범위의 최댓값에 맞게 배열을 만들고
for문을 하나만 사용해 a와 b를 구하는 방식으로 했다.

시간 초과에 대한 문제는 항상 어려운거 같다.
이에 대해 좀 찾아보니 보통 러프하게 1초에 1억의 연산을 하는데
이는 $10^8$이다. 이 문제의 입력값의 경우 최대 $10^5$인데
$O(n)$의 경우에는 $1/10^3$초가 걸린다고 할 수 있고,
$O(n^2)$의 경우에는 $10^2$초가 걸리므로 어림도 없다.

그리고 소수를 구할때 사용하는 알고리즘인 에라토스테네스의 체에 대해서 정리하려 한다.
이전 소수에 관련된 문제를 풀때도 검색을 하며 본적은 있으나 굳이 안써도 풀 수 있길래 쓸 생각은 안했지만 속도 측면에서도 그렇고 쓰는게 더 나은 방법 같다.

final static int MAX = 1000001;
static boolean[] isPrime = new boolean[MAX];

//에라토스테네스의 체
static void sieveOfEratosthenes() {

	//우선 모든 수를 true, 소수로 할당
    Arrays.fill(isPrime, true);
    //0과 1은 소수가 아니므로 false
    isPrime[0] = isPrime[1] = false;

	//2부터 MAX의 제곱근까지 반복
    //각각의 배수들을 지워간다
    for (int i = 2; i * i < MAX; i++) {
		//i가 소수일 때
        if (isPrime[i]) {
        	//i*i미만은 이미 처리되었으므로 i*i부터 시작
            //i의 배수들을 지워간다
            for (int j = i * i; j < MAX; j += i) {
                isPrime[j] = false;
            }                
        }
    }

}