17103 골드바흐 파티션 JAVA

이번 문제는 골드바흐의 추측 문제를 풀고 오는 길이라 매우 간단하게 해결할 수 있었다.

 

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

 

나는 먼저 100만까지 모든 소수를 먼저 구하고, 파티션의 개수를 구하는 방식으로 구현하였다.

아래는 에라토스테네스의 체를 이용하여 소수를 구하는 가장 흔하면서 간단한 코드이다.

 

int max = 1_000_000;
int[] prime = new int[max];
boolean[] check = new boolean[max+1];
int k = 0;

for(int i = 2; i <= max; i++) { // 에라토스테네스의 체
    if(check[i]) continue;
    else
        prime[k++] = i;
    for(int j = i * 2; j <= max; j+=i)
        check[j] = true;
}

 

이 역시 j = i * i;로 하면 정수의 범위를 넘어가면서, 오버플로우가 될 것 같아서 i * 2로 하였다.

추가로 이미 지워진 수라면 continue를 하였다. 내 생각엔 이게 속도향상에 영향이 있어보였는데 쓰고 안쓰고가 이상하게 속도가 동일했다..

 

어쨌든 이렇게 소수를 먼저 구하고 아래와 같이 파티션의 개수를 구한다.

단 문제의 조건을 읽어보면 3 + 7, 7 + 3은 같은 것으로 간주하여 1개라는건데 이건 그냥 N의 절반까지만 반복하면 된다.

 

import java.io.*;
public class M17103 {
    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 max = 1_000_000;
        int[] prime = new int[max];
        boolean[] check = new boolean[max+1];
        int k = 0;

        for(int i = 2; i <= max; i++) { // 에라토스테네스의 체
            if(check[i]) continue;
            else
                prime[k++] = i;
            for(int j = i * 2; j <= max; j+=i)
                check[j] = true;
        }

        int T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            int N = Integer.parseInt(br.readLine());

            int num, cnt = 0;
            for(int i = 0; (num = prime[i]) * 2 <= N; i++){
                if(!check[N - num])
                    cnt++;

            }

            bw.write(cnt + "\n");
        }
        bw.flush();
        bw.close();
    }
}

 

 

 

 

계속해서 시간을 조금씩 줄여봤는데 236ms까진 가능했다. 그래도 자바 언어중에선 다른 채점들과 비교해서 빠른 속도인 거 같아서 여기서 만족하고 끝내겠다.