[백준] 17103 _ 골드바흐 파티션 (Java)

정답코드와 결론은 맨 아래에-!!

이 문제는 2 이상의 짝수는 소수 두 개의 합으로 이루어져있다는 원리를 이용한 문제이다.

문제 이해

'=' 의 개수가 곧 파티션의 개수
예를 들어보면 아래와 같은 방식으로 2보다 큰 짝수가 소수 두 개의 합으로 이루어진 것을 알 수 있다.
또한, 합치면 짝수가 나오는 두 소수의 세트가 몇 개인지가 파티션의 개수이다.

( 1 )  6 = 3+3
( 1 )  8 = 3+5
( 2 )  10 = 3+7 = 5+5
( 1 )  12 = 2+6
( 2 )  14 = 3+11 = 5+7

입출력 형식

[ 입력 ]
- 테스트케이스(T) = 파티션의 개수를 구할 짝수를 몇 개 입력 받을 것인가?
- 짝수(N) = 소수 두 개의 합으로 이루어진 숫자

[ 출력 ]
입력받은 짝수의 파티션 개수 = (짝수를 이루는) 소수 합의 개수

문제점

문제를 풀면서 느낀 가장 큰 문제점 2가지가 있다.

1. [ 2 ~ 입력받은 짝수 ] 의 소수를 어떻게 구하지?
   : 이 문제에 대해서는 에라토스테네스의 체를 이용하였다.
   이 문제의 하단에 있는 알고리즘에서도 에라토스테네스의 체를 이용하는 것을 권장하고 있으며, 가장 확실하고 빠르게 소수를 구할 수 있는 방법이었다.

2. 짝수는 다양한 소수로 이루어져있는데 그걸 하나하나 어떻게 찾지?
   ex) 5 = (2, 3)의 소수로 이루어져 있다.
   이 때 2와 3까지는 구해도 2+2를 해보고 2+3을 해보고 3+3을 해보는 방법을 이용할까 하는 생각을 했지만 이렇게 중첩해서 계산하면 시간복잡도 가 너무 높아졌다.
   : [ 2 ~ 입력받은 짝수 ] 중 하나의 수를 n이라고 했을 때 2부터 n까지 돌면서 소수인 수 ( i )를 찾고 ( n-i )도 소수인지 확인한다.

코드풀이

[ 에라토스테네스의 체 ] 함수 부분

  static void isPrime(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
      if (prime[i]) {
        continue;
      }
      
      for (int j = i * i; j <= n; j += i) {
        prime[j] = true;
      }
    }
  }

1. static으로 짝수 n개의 boolean타입 배열을 생성
2. for문을 2부터 n의 제곱근( = n의 반)만큼 돈다.
3. 배열의 값이 true일 경우( = 소수가 아닐 경우) => continue
4. false일 경우 ( = 소수일 경우) 해당 수( i )를 제외한 i의 배수들을 true(소수가 아닌 수)처리 해준다.

ex) i = 2 ~ 6 일 때, 소수인 2,3,5(false) 의 배수를 true 처리

• 배열의 기본 값은 false 이다.
• array[0] = array[1] = true; 를 통해 0과 1을 소수가 아닌 수로 처리해준다.
• 배열에서 소수가 아닌 수를 false 처리하기 위해서는 배열의 기본 값을 true 로 바꿔야 하는데, 그러려면 불필요한 for문을 한번 더 작성해야 한다.
• 따라서 반대로 소수가 아닌 수를 true처리하고, 소수인 수를 false 처리하는 것으로 정의하였다.

---

[ 전체코드 ]

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

public class App {

  static boolean[] prime;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

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

    for (int t = 0; t < tc; t++) {
      int n = Integer.parseInt(br.readLine());
      int count = 0;
      prime = new boolean[n + 1];
      prime[0] = prime[1] = true;
      isPrime(n);

      for (int i = 2; i <= n / 2; i++) {
        if (!prime[i] && !prime[n - i]) {
          count++;
        }
      }
      sb.append(count).append("\n");
    }

    System.out.println(sb);
  }

  static void isPrime(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
      if (prime[i]) {
        continue;
      }
      for (int j = i * i; j <= n; j += i) {
        prime[j] = true;
      }
    }
  }
}

[ 변수 정리 ]

• tc : 입력받을 짝수의 개수
• n : 입력받은 짝수
• count : 열려 있는 창문의 개수 ( = 약수를 홀수개 가지고 있는 짝수의 개수)
• prime : boolean타입으로 에라토스테네스의 체를 통해 소수를 확인할 배열

[ 코드 해석 ]

1. 에라토스테네스의 체로 소수를 담아둘 boolean타입 변수는 main과 isPrime함수에서 모두 사용하므로 가장 위에 static으로 선언한다.
   ( static으로 선언 시 프로그램 실행과 동시에 생성된다.)

2. Scanner보다 BufferedReader가 더 빠르게 동작하기 때문에 BufferedReader로 입력받는 객체를 생성해준다.

3. 여러 개의 수에 대한 답을 출력해야하기 때문에 StringBuilder라는 객체를 생성하여 답을 넣고 한번에 출력한다.

4. 가장 먼저 몇 개의 수를 입력 받을지를 변수 tc에 입력받는다.

5. tc번을 for문을 돌면서 변수 n에 짝수를 하나씩 입력받는다.

6. n의 홀수인 약수 개수를 구해야하기 때문에 짝수 n을 입력받을 때마다 count도 같이 초기화 해준다.

7. static으로 선언한 prime 배열을 짝수 개수 n개만큼으로 선언한다.
   그리고 0과 1은 소수가 아니기 때문에 for문에 포함되지 않고, 배열 선언과 동시에 true처리한다.

8. for문을 2부터 n의 반 (n/2)까지 돌리면서 n을 조합하는 소수인 두 수를 찾기 위해서 i와 n-i가 모두 array배열에 false값을 가지고 있는지 (에라토스테네스의 체로 소수인지 검사한 배열) 확인한다.

9. 만약 i와 n-i가 모두 소수라면 count에 1을 추가한다.

10. 입력된 짝수에 대한 답을 sb라는 객체에 넣어주고 for문이 모두 돌아간 후 한번에 출력한다.

• StringBuilder는 .append() 메소드를 통해 입력받은 값을 형식 그대로 가지고 있는 객체라고 생각하면 된다.