[Algorithm] 백준 6588 - 골드바흐의 추측 (JAVA)

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

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> arr = new ArrayList<>();
    static ArrayList<Integer> chk = new ArrayList<>();
    static int[] prime;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        while (true){
            n = sc.nextInt();
            if (n == 0) break;
            arr.add(n);
        }
        prime = new int[100001];
        isPrime();
        for (int i = 0; i < arr.size(); i++) {
            dfs(arr.get(i), 0, 1);
        }
    }

    public static void dfs(int num, int start, int end) {
        int a = chk.get(start);
        int b = chk.get(end);
        if (a >= num/2) {
            System.out.println("Goldbach's conjecture is wrong.");
            return;
        }
        else if (a+b == num) {
            System.out.println(num + " = " + a + " + " + b);
            return;
        }
        else if (a+b > num) {
            dfs(num, start+1, start+2);
        }
        else {
            if (end == chk.size()-1) dfs(num,start+1, start+2);
            else dfs(num, start, end+1);
        }

    }

    public static void isPrime() {
        prime[0] = prime[1] = 1;
        for (int i = 2; i < prime.length; i++) {
            if (prime[i] == 0) {
                if (i % 2 == 1) chk.add(i);
                for (int j = i * 2; j < prime.length; j += i) {
                    prime[j] = 1;
                }
            }
        }
    }
}

• stackoverflow, 시간 초과 오류 발생. 입력 값이 10만이다보니, 재귀를 피해야 한다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> arr = new ArrayList<>();
    static ArrayList<Integer> chk = new ArrayList<>();
    static int[] prime;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        while (true){
            n = sc.nextInt();
            if (n == 0) break;
            arr.add(n);
        }
        int max = Collections.max(arr);
        prime = new int[max+1];
        isPrime();
        boolean key;
        for (int j=0; j<arr.size(); j++) {
            key = false;
            for (int i = 3; i <= arr.get(j) / 2; i++) {
                if ((i + arr.get(j)-i) == arr.get(j)) {
                    if (prime[i] == 0 && prime[arr.get(j) - i] == 0) {
                        System.out.println(arr.get(j) +" = " + i + " + " + (arr.get(j)-i));
                        key = true;
                        break;
                    }
                }
            }
            if (!key) System.out.println("Goldbach's conjecture is wrong.");
        }

    }

    public static void isPrime() {
        prime[0] = prime[1] = 1;
        for (int i = 2; i < prime.length; i++) {
            if (prime[i] == 0) {
                if (i % 2 == 1) chk.add(i);
                for (int j = i * 2; j < prime.length; j += i) {
                    prime[j] = 1;
                }
            }
        }
    }
}

• 입력받은 개수 만큼 for문을 실행하며, n = a+b 구조이기 때문에 a가 n / 2일 때 까지 비교
• a 번째와 n-a번째가 모두 소수이면 필터링하여 출력
• 사용 알고리즘 (에라토스테네스의 체 + a 번째 n-a 번째 소수판별)