[Java] 백준알고리즘 #17103 골드바흐 파티션

백준알고리즘 #17103 골드바흐 파티션

어떤 짝수 n 을 두 소수의 합으로 나타낼 수 있는데, 이 두 소수의 순서쌍의 개수를 구하는 문제이다.

 

앞서 사용했었던 유클리드호제법을 이용해 소수를 도출해서 계산했더니 시간 초과 에러가 나왔다.

때문에 이번에는 에라토스테네스의 체를 이용해 소수를 도출해보았다.

2020.12.08 - [Java/백준알고리즘] - 백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체)

백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체)

 

보다 최적화된 에라토스테네스의 체 코드를 만들어보자.

for (int i = 0; i < n; i++) {
    int a = sc.nextInt();
    int count = 0;
    int[] ary = new int[a + 1];
    ary[0] = ary[1] = 1;

    for (int j = 2; j * j <= a; j++) { // 에라토스테네스의 체

        for (int k = j + j; k <= a; k += j) {
            ary[k] = 1;
        }

    }
}

앞서 유클리드 호제법을 이용한 문제를 해결하면서 소수의 판별은 근접한 제곱수를 이용하여 반복문 횟수를 줄일 수 있다는 것을 확인했다.

에라토스테네스의 체를 이용해 배열을 만들어 소수에 해당하는 인덱스 값은 0,

소수가 아닌 합성수라면 1로 만들어주면 된다.

 

0과 1은 소수가 아니므로 1로 초기화 해둔 후, 2부터 a에 가장 가까운 제곱수까지 반복한다.

다시 반복문을 통해 어떤 수 x 2 부터 a보다 작은 k까지 곱해준다 (k = k + j 로 곱셈을 나타냄)

이때 곱한 값(k)는 합성수이므로 k에 해당하는 인덱스의 값을 1로 바꿔준다.

이 과정을 반복하면 ary배열에서 소수는 0, 합성수는 1이 될 것이다.

 

이제 다시 반복문을 통해 두 수의 합을 계산해주면 된다.

for (int j = 2; j <= a / 2; j++) {
    if (ary[j] == 0 && ary[a - j] == 0) {
        count++;
    }
}

j번째의 값과 a-j 번째의 값을 더하면 a가 되므로, 이 두 값이 소수라면 count를 증가시켜 답을 도출한다.

이 때 반복문의 범위는 a/2까지가 되는데, a까지로 두게 되면 (2,3)과 (3,2)가 중복으로 계산되는 경우가 생긴다.

그렇다고 a/2보다 작은 범위를 설정하게 되면 6의 경우 (3,3)인 경우가 있는데 이 경우가 포함이 되지 않으므로

"작거나 같다" 로 범위를 지정해주어야 한다.

 

전체 코드를 보면 다음과 같다.

 

// 해설참조 : sehyeok.tistory.com 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int count = 0;			// 결과값(순서쌍의 개수)을 담을 변수
            int[] ary = new int[a + 1];
            ary[0] = ary[1] = 1;		// 0과 1은 소수가 아님

            for (int j = 2; j * j <= a; j++) { // 에라토스테네스의 체
                for (int k = j + j; k <= a; k += j) {
                    ary[k] = 1;
                }
            }
            for (int j = 2; j <= a / 2; j++) {	// 두 소수를 더했을 때 a가 나오는 경우 확인
                if (ary[j] == 0 && ary[a - j] == 0) {
                    count++;
                }
            }
            System.out.println(count);
        }
        sc.close();
    }
}