[백준/Java] #17103 골드바흐 파티션

 

 

문제

 

 

N 미만인 소수 a와 b의 합이 N이 되는 경우의 수를 구해야 하는데, 예제에서 알 수 있듯 a와 b는 같은 수가 될 수 있다.

 

예를 들면 10 미만의 소수는 {2, 3, 5, 7}이 있고

{3, 7}, {5, 5}의 합이 10이 되므로 골드바흐 파티션의 개수는 2가 된다.

 

 

 

코드

 

문제를 처음 봤을 때 시간제한 0.5초를 보고 설마 했는데, 역시나 첫 시도는 시간초과가 발생했다.

소수의 합이 N이 되는 경우를 브루트 포스 방식으로 탐색했기 때문이다. 당연한 결과 😂

 

두 번째 시도는 `LinkedHashSet`에 소수를 저장한 뒤 조건에 맞는 경우만 count를 증가시키는 방법을 사용했다.

static LinkedHashSet<Integer> primes = new LinkedHashSet<>();

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

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

    while (T-- > 0) {
        int N = Integer.parseInt(br.readLine());
        makePrime(N);
        sb.append(getCount(N) + "\n");
    }
    System.out.println(sb);
}

//소수 구하기(에라토스테네스의 체)
static void makePrime(int N) {
    boolean[] arr = new boolean[N]; //0 ~ N-1
    arr[0] = arr[1] = true;

    for (int i = 2; i < Math.sqrt(N); i++) {
        if (arr[i]) continue;
        for (int j = i * i; j < arr.length; j += i) {
            arr[j] = true;
        }
    }
    for (int i = 2; i < arr.length; i++) {
        if (!arr[i]) primes.add(i); //소수인 경우 primes에 추가
    }
}

//소수의 합이 N이 되는 경우의 수 구하기
static int getCount(int N) {
    int count = 0;

    for (Integer a : primes) {
        int b = N - a;
        if (primes.contains(b) && b >= a) count++;
    }
    return count;
}

 

나름 시간을 줄여보겠다고 중복된 값은 추가되지 않도록 `LinkedHashSet`을 사용했다.

간신히 성공하긴 했는데 뭔가 굉장히 비효율적인 느낌이 들어서 다른 방법을 사용하고 싶었다.

 

N을 입력받을 때마다 소수 판별을 하는 것과 Set에 소수를 넣은 뒤 파티션의 개수를 구하는 알고리즘을 바꿔보면 될 것 같았다.

 

 

그래서 세 번째 시도.

static boolean[] arr = new boolean[1000001]; //0 ~ 입력 가능한 최댓값

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

    makePrime();
    int T = Integer.parseInt(br.readLine());

    while (T-- > 0) {
        int N = Integer.parseInt(br.readLine());
        int count = 0;
        for (int i = 2; i <= N / 2; i++) { //반으로 나눠 앞부분만 탐색
            if (!arr[i] && !arr[N - i]) count++;
        }
        sb.append(count + "\n");
    }
    System.out.println(sb);
}

//소수 구하기
static void makePrime() {
    arr[0] = arr[1] = true;

    for (int i = 2; i <= Math.sqrt(arr.length - 1); i++) {
        if (arr[i]) continue;
        for (int j = i * i; j < arr.length; j += i) {
            arr[j] = true;
        }
    }
}

 

범위 내 소수를 모두 구한 뒤 입력을 받도록 하여 입력 횟수가 많더라도 소수 판별은 1회만 실행된다.

 

a + b = N일 때 b = N - a 이므로 `!arr[i] && !arr[N - i]`를 충족하면 소수인 두 수의 합이 N이 된다.

또한 a와 b의 순서는 파티션에 영향을 주지 않기 때문에 N 미만의 전체 인덱스를 탐색하지 않고 절반만 확인한다.

 

 

 

위에서부터 순서대로 시도 3, 시도 2의 풀이인데 시간과 메모리의 차이가 크다.

알고리즘 문제는 난이도가 올라갈수록 효율성에 대한 고민을 많이 해야하는 것 같다.