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

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

17103번: 골드바흐 파티션

---

1. 풀이

골드바흐의 추측과 거의 똑같은 문제이다.

 

주의 할 점은 두 소수의 순서만 다른 것은 같은 파티션으로 본다는 것이다.

 

우선, 에라토스테네스의 체를 이용해 MAX까지 소수를 구하고 나서, 두 소수의 순서가 바뀐 것은 count해주지 않으면 된다.

 

a와 b가 N을 구성하는 소수라면, a를 N/2이하까지만 탐색하면 된다.

 

즉, N이 10이라면, 10의 1/2인 5까지만 탐색을 해주면 된다.

 

그 외에도 전부 result에 더하고 짝수면 나누기 2를 해주고, 홀수면 나누기 2하고 플러스 1을 해줘도 가능하다.

 

---

2. 코드

import java.util.*;

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

        int T = sc.nextInt();
        ArrayList<Integer> prime = new ArrayList<>();
        boolean[] check = new boolean[1000001];

        // 소수 구하기.
        check[0] = check[1] = true;
        for(int i = 2; i < 1000001; i++){
            if(check[i] == false){
                prime.add(i);
                for(int j = i+i; j < 1000001; j+=i)
                    check[j] = true;
            }
        }

        // N/2까지만 탐색하는 방법.
        while(T-- > 0){
            int N = sc.nextInt();
            int result = 0;
            for(int i = 0; prime.get(i) <= N/2 ; i++){
                // 골드바흐가 맞다면
                if(check[N - prime.get(i)] == false) {
                    result++;
                }
            }
            System.out.println(result);
        }

        // 다 더하는 방법.
//        while(T-- > 0){
//            int N = sc.nextInt();
//            int result = 0;
//            for(int i = 0; prime.get(i) <= N ; i++){
//                // 골드바흐가 맞다면
//                if(check[N - prime.get(i)] == false) {
//                    result++;
//                }
//            }
//
//            if(result % 2 == 0) // 짝수면
//                System.out.println(result/2);
//            else // 홀수면
//                System.out.println((result/2)+1);
//        }
        
        sc.close();
    }
}