[백준] JAVA 자바 : 골드바흐의 추측 (6588번)

---

후… 이 문제 가지고 거의 2시간 가량을 손에 쥐고 있었다… 나는 겨우 이 정도밖에 안 되는가…
문제 자체는 어려운 게 아닌데 시간 제한이 0.5초라서 상당히 타이트했다… 진짜 온갖 방법을 다 써서 나도 겨우 해결했는데 그래도 시간이 1748ms나 걸린다…ㅋㅋㅋㅋㅋ 자바 순위 600명 중 500등 정도 되는 듯…………ㅋㅋㅋㅋ쿠ㅜㅜ

나는 최대 수인 1000000까지 모두 담을 수 있는 배열을 만들고, 그 배열이 해당 수가 소수인지(true) 합성수인지(false) 나타내게 만든 다음, 이제 수 N이 들어올 때마다 3부터 차례로 2씩 증가시키면서 그 수와 N에서 그 수를 뺀 값이 모두 소수인지 확인해서 출력하는 알고리즘을 사용했다. 그런데 사실 다른 코드를 봐도 비슷한 알고리즘인 것 같은데 왜 나랑 3배 이상 시간이 차이나는 걸까…?

여하튼 아직까지는 나는 이 정도가 한계인가보다… 나중에 실력을 더 키워서 다시 도전해서 시간을 더 줄여봐야겠다…

 

package BJoon.수학1;

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

public class Goldbach_6588 {
    static final int MAX = 1000000;
    static boolean[] n_list = new boolean[MAX + 1]; // 소수인지 아닌지를 담을 배열. true = 소수, false = 소수 아님
    static StringBuilder sb = new StringBuilder();
    
    public static void goldbach(int num) {
        for (int i=3; i<=num/2; i+=2) { // 소수를 검사하는데 그 수는 홀수여야 하므로
            int a = num - i; // 두 번째 수는 해당 수 num에서 i를 뺀 값이다
            if (n_list[i] && n_list[a]) { // 두 수가 모두 소수라면
                sb.append(i).append(" + ").append(num-i); // 출력할 StringBuilder에 담는다
                return;
            }
        }
        
        // 만약 반복문을 다 돌았는데도 홀수인 두 소수 짝을 찾지 못했다면
        sb.setLength(0);
        sb.append("Goldbach's conjection is wrong."); // 골드바흐의 추측은 틀린 것이 된다
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        Arrays.fill(n_list, true);
        n_list[0] = false;
        n_list[1] = false;
        for (int i=2; i<=Math.sqrt(1000000); i++) {
            if (n_list[i]) {
                for (int j=2; j*i<=1000000; j++) {
                    n_list[i*j] = false; // 합성수를 찾으면 그 배수를 모두 합성수로 표기한다
                }
            }
        }
        // 여기까지가 1000000까지 모든 수가 소수인지 합성수인지 나타내는 배열인 n_list를 구성하는 과정!
        
        int N;
        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0) break;
            
            sb.append(N + " = ");
            goldbach(N);
            System.out.println(sb);
            sb.setLength(0);
        }
        
        br.close();
    }

}

 

로그인

 

 

작성일자: 2023-09-09