백준 17103 골드바흐 파티션 [JAVA]

문제 해석

• 이 문제는 골드바흐의 추측을 기반으로 골드바흐의 파티션을 찾으면 되는 것이다.
• 문제를 풀기 전 골드바흐의 파티션이 무엇인지 이해를 해야하는데, 처음 읽었을 땐 생소한 느낌이었지만, 읽어보면 간단하다.
• 일단, 입력받을 2보다 큰 짝수의 개수(T)를 입력받고 T개 만큼 2보다 큰 짝수를 입력 받는다.
• 입력받았다면, 해당 골드바흐 파티션의 개수를 구하면 되는데 골드바흐 파티션이란? 2보다 큰 짝수(N)는 두 소수의 합으로 나타낼 수 있는데 그 짝수 N가 나타낼 수 있는 두 소수의 합의 쌍의 개수를 출력하면 되는 문제이다.
• 단, 순서만 다르고 같은 두 소수의 합으로 나타낸 경우는 같은 파티션으로 두번 세지 않는다.

코드

import java.io.*;

public class Main {
    static boolean[] primeArray = new boolean[1000001];

    //입력&출력 부분
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        findPrime();

        int T = Integer.parseInt(br.readLine()); //테스트의 개수
        
        for(int i = 0; i < T; i++){
        
            int N  = Integer.parseInt(br.readLine()); //2보다 큰 짝수

            int partitionCount = 0; // 파티션의 짝수

            if(N % 2 == 0 && N != 0) { //짝수인 경우만
            // 순서만 다르고 두 소수가 같은 경우는 같은 파티션임으로 N/2한다.
                for (int j = 2; j <= N / 2; j++) {
                    // 두 수의 합이 N일때 그 두수가 모두 소수일 때
                    if (!primeArray[j]) { // 소수일 때
                        if (!primeArray[N - j]) { // N- 소수 = 소수일때
                            partitionCount++;
                        }
                    }
                }
                bw.write(partitionCount + "\n");
            }else{
                bw.write(0 + " \n");
            }
        }

        br.close();

        bw.flush();
        bw.close();
    }
    
    //소수 판별 배열 만다는 메소드
    static void findPrime(){
        primeArray[0] = primeArray[1] = true;

        for (int i = 2; i < primeArray.length; i++) { // 미리 골드바흐의 추측에 따른 소수값 구하기

            if (primeArray[i] == false) {

                for (int j = 2; i * j < primeArray.length; j++) {
                    primeArray[i * j] = true;
                }
            }

        }
    }
}

• 이 문제는 전 POST였던 4948-베르트랑 공준의 연장선의 느낌이었다.
• 일단 소수를 판별하는 배열을 만들어놓고, 입력값을 받아 소수인지 판별한다.
• 주의해야할 점은 순서만 다르고 두 소수가 같은 경우는 같은 파티션임으로 N/2한 점이다.

결과

느낀 점

• 여전히 시간과 메모리를 많이 쓰는 코드만 작성하게 되지만,,, 그래도 이 문제는 전 포스트와 연결된 부분이 많아서 이해하는데 어렵지 않았다.