[java] 17103 골드바흐 파티션

 

이 문제는 짝수는 두 개의 소수로 이루어져 있다는 골드바흐 파티션의 개수를 출력하는 문제이다.

 

문제는 간단하나 요구조건을 생각해야한다.

 

1. 3, 7  7, 3 철럼 같은 수로 이루어진 수는 1개로 취급한다.

 

2. 0.5초의 시간으로 걸리는 시간을 고려한다.

 

이 두 조건이 은근 까다롭다. 특히 제한시간이 짧아 시간초과가 많이 떳다.

 

다음은 옳게 작동하나 시간초과가 뜨는 코드이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            int count = 0;
            for (int j = 0; j <= n; j++) {
                if (isPrime(j) == false) {
                    continue;
                }
                for (int k = 0; k <= n; k++) {
                    if (isPrime(k)) {
                        if ((j + k) == n && (j + k) % 2 == 0) {
                            if (j > k) {
                                continue;
                            }
                            count++;
                        }
                    }
                }

            }
            System.out.println(count);
        }

    }

    public static boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

}

 

위 코드는 시간초과가 뜨는 코드이다. 

 

위에서 중복되는 반복문을 제거하고, isPrime도 메소드를 제거하여 좀 더 빠르게 구성하였다.

 

또한 미리 배열을 통해 소수만으로 구성된 배열을 사용하여 연산량을 더욱 줄였다.

 

그리고 소수로만 구성된 배열 n과 n-j를 비교함으로서 합으로 n을 형성하는 소수들을 구하는 동시에 

 

 n/2까지 반복문 범위를 정함으로서  3,7 7,3과 같이 겹치는 값을 제거했다. (배열에는 음수자릿수가 없기 때문)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));

        int N = Integer.parseInt(br.readLine());
        boolean arr[] = new boolean[1000001];
        //n의 최대값임 1000000크기를 가지는 boolean타입의 배열을 선언
        
        for (int i = 0; i < 1000001; i++) {
            if (isPrime(i)) {
                arr[i] = true;
                // i가 소수일 경우 true로 표시
            }
        }
        

        for (int i = 0; i < N; i++) {

            int n = Integer.parseInt(br.readLine());
            int count = 0;
            //소수의 개수를 세는 변수

            for (int j = 2; j <= n / 2; j++) {
            	// n/2까지로 범위를 제한함으로서 중복연산과 값 도출을 방지
                if (arr[j] && arr[n - j]) {
                	// j번째와 n-j번째를 비교함으로서 if문 줄이기
                    count++;
                }
            }
            System.out.println(count);
        }

    }

    public static boolean isPrime(int num) {
    	//소수를 구하는 메소드, Math.sqrt를 제거함으로서 속도 증가.
        if (num < 2) {
            return false;
        }
        for (int i = 2; i*i <= n; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

}