6588 골드바흐의 추측 JAVA

이번 문제는 수학적 지식이 어느정도 요구하는 문제라고 생각한다.

 

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

우선 이 문제를 0.5초 안에 구하려면 에라토스테네스의 체와 같은 효율적인 알고리즘을 알고 있어야 한다고 생각한다.

무식하게(?) 순회로는 절대 풀수 없다.

 

또한 나는 이 문제를 풀면서 최대한 시간 복잡도를 지키면서 구현했는데 몇번 시간초과가 났다. 그런데 에라토스테네스의 체를 이용하여 구현했으므로 로직이 느려서 그런건 아닌 거 같아서 이때까지 계속 출력할 때 써왔던 StringBuilder 대신, 자바에선 가장 빠룬 BufferedWriter로 출력하니 시간초과 없이 통과가 됐었는데 약간 어이가 없었다.. 

 

일단 나는 이 문제를 에라토스테네스의 체를 구하는 부분과 골드바흐의 추측을 구하는 부분으로 총 2부분으로 나누어 간단히 설명하겠다.

아래 코드는 문제에서 주어진 1천만까지의 모든 소수를 구하는 코드이다.

 

나는 이번 문제에선, 요즘 내가 너무 자료구조만을 이용해서 쉽게 해결하려고 하는 것 같아서 배열을 이용해서 구현해봤다.

int max = 1000000;
int[] prime = new int[max];
boolean[] check = new boolean[max+1];
int cnt = 0;

for(int i = 2; i <= max; i++) {
    if(!check[i]) prime[cnt++] = i;
    for(int j = i * 2; j <= max; j+=i)
        check[j] = true;
}

에라토스테네스에 대한 설명은 하지 않겠다.

다만 여기서 주의해야할 점은 max가 1천만이므로 중첩 반복문 내의 j의 값을 i^2로 초기화하면 int의 범위를 넘어가기에 주의하는 것이 좋다. 따라서 약간은 겹치더라도 i * 2로 하였다. 또한 그냥 prime[cnt++] 과 같이 하지 않고, 단순히 prime[i]로 값을 입력받으면 아래에서 식을 구할 때 쓸데없이 0을 순회할 수 있으므로, 순차적으로 입력을 받아놓는 것이 좋다. 아무튼 이렇게 하면, 범위내의 모든 소수를 구할 수 있다.

 

for(int i = 0; i < 100_000; i++) {
    int N = Integer.parseInt(br.readLine());
    if(N == 0) break;

    boolean goldbachWasWrong = true;
    for(int j = 0; prime[j] != 0; j++) {
        int num = prime[j];
        if(!check[N - num]) {
            bw.write(N + " = " + num + " + " + (N - num));
            goldbachWasWrong = false;
            break;
        }
    }
    if(goldbachWasWrong)
        bw.write("Goldbach's conjecture is wrong.");

    bw.write("\n");
}

 

이 코드는 마지막으로 에라토스테네스의 체가 옳은지 구하는 코드이다.

내가 위에서 작성한 코드로 인해 논리형 배열인 check엔 true와 false로 소수가 구분되어 있다는 점을 이용하자.

따라서 N이 8일 때, i가 3이라면 check[8-3]이 false인지 확인하면 된다.

마지막으로 골드바흐의 추측이 틀렸는지 검사하면 된다.

 

import java.io.*;
public class M6588 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int max = 1000000;
        int[] prime = new int[max];
        boolean[] check = new boolean[max+1];
        int cnt = 0;

        for(int i = 2; i <= max; i++) {
            if(!check[i]) prime[cnt++] = i;
            for(int j = i * 2; j <= max; j+=i)
                check[j] = true;
        }

        for(int i = 0; i < 100_000; i++) {
            int N = Integer.parseInt(br.readLine());
            if(N == 0) break;

            boolean goldbachWasWrong = true;
            for(int j = 0; prime[j] != 0; j++) {
                int num = prime[j];
                if(!check[N - num]) {
                    bw.write(N + " = " + num + " + " + (N - num));
                    goldbachWasWrong = false;
                    break;
                }
            }
            if(goldbachWasWrong)
                bw.write("Goldbach's conjecture is wrong.");

            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }
}

 

하루종일 스프링을 공부하고, 새벽 1시에 골드바흐를 풀고 있자니 너무 힘들었다..

어쨌든 풀었으니 빨리 자야겠다ㅠㅠ