[JAVA/6588번] 골드바흐의 추측

문제

입력 및 출력

풀이

import java.io.*;
import java.util.*;

class Main {
    // 소수를 판별하기 위한 메서드
    public static boolean PrimeNumber(int number) {
        // number가 1인경우 소수가 아니기 때문에 false
        if (number < 2) {
            return false;
        }

        // 2부터 i의 제곱이 넘어온 number변수보다 작을 경우 반복문을 수행
        for (int i = 2; i * i <= number; i++) {
            // 나머지가 0일 경우 소수가 아니므로 false
            if (number % i == 0) {
                return false;
            }
        }

        // 그 외의 경우 number는 소수이기 때문에 true 
        return true;
    }

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

        StringBuilder sb = new StringBuilder();

        // 1000000크기를 갖는 소수를 담을 배열
        int[] array = new int[1000001];

        // 소수를 담을 리스트를 선언한다.
        List < Integer > list = new ArrayList < > ();

        // array의 크기만큼 반복문을 돌며, PrimeNumber메소드를 호출해서 소수를 리스트에 넣는다.
        for (int i = 1; i < array.length; i++) {
            if (PrimeNumber(i) == true) {
                list.add(i);
            }
        }

        // while 반복문을 끝내기 위한 변수
        boolean check = true;
        while (check) {
            // 테스트 케이스 N
            int N = Integer.parseInt(br.readLine());

            // N이 0일경우 반복문을 종료
            if (N == 0) {
                check = false;
                break;
            }

            // A와 B변수 선언
            int A = 0;
            int B = 0;

            // 리스트의 사이즈만큼 반복
            for (int i = 0; i < list.size(); i++) {
                // 현재 인덱스가 N보다 클 경우 continue
                if (list.get(i) > N) {
                    continue;
                }
                // 그 외의 경우 A에는 가장 작은 원소를 B에는 가장 큰 원소를 넣는다.
                for (int j = list.size() - 1; j >= 0; j--) {
                    if (N == (list.get(i) + list.get(j))) {
                        A = list.get(j);
                        B = list.get(i);
                    }
                }
            }
            // A또는 B가 0이 아닐경우
            if (A != 0 && B != 0) {
                System.out.println(N + " = " + A + " + " + B);
            }
            // 그 외의 경우
            else {
                System.out.println("Goldbach's conjecture is wrong.");
            }
        }
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법

• 기존의 소수구하기 문제를 해결했던 방법을 응용하여 문제를 해결하려 노력했다.
  결론적으로 50%에서 시간초과가 발생했다. 이를 해결하려 노력했지만 아직 해결하지 못했다.

  이번 문제의 핵심은 A는 가장 작은 소수여야하고, B는 N보다 작으면서 가장 큰 소수로 구성되어야 한다는 것이다. 문제가 완벽하게 해결된 후 다시 정리할 예정이다.