Algorithm/수학

백준 알고리즘 [자바] 골드 바흐의 추측 9020

한둥둥 2022. 10. 7. 15:30

골드 바흐의 추측 9020

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Baekjoon9020 {
    static boolean checkArr[]= new boolean[10001];
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        Scanner scan = new Scanner(System.in);
        
        
        int n = scan.nextInt();
        soloCheck();
        for(int i=0;i<n;i++){   
            int n1 = scan.nextInt();
            sumSolo(n1);
        }
        bw.flush();
        bw.close();
        scan.close();
    }
    static void sumSolo(int num)throws IOException{
        int rt = num/2;
        int lt = num/2;
        while(true){
            if(!checkArr[rt]&&!checkArr[lt]){
                bw.write(lt+" "+rt+"\n");
                break;
            }
            rt++;
            lt--;
        }
    }
    static void soloCheck(){
        for(int i=2;i<checkArr.length-1;i++){
            if(checkArr[i]) continue;
            for(int j=i*i;j<checkArr.length;j+=i){
                checkArr[j]=true;
            }
        }
    }
}

1.우선적으로 소수 구하기 문제처럼 soloCheck배열을 통해서 배열이 소수인지 아닌지 판별을 해주었다.

이미 true인 아이들은 찾아서 들어 갈 필요가 없기 때문에 즉, 한번 쭉 이전에 지난간거여서 복잡도를 단축시키기위해 continue로 위로 올려주었다. 

 

2. 그 후에 sumSolo라는 함수에서 더해주는 값을 찾았고 절반을 기준으로 플러스 마이너스 해주면서 해당하는 값이 소수인 경우에 출력되도록 만들어주었다. 절반값이 둘다 소수라면 두 수를 더해주면 내가 원하는 숫자가 나올 것이다. 왜냐면 동시에 lt,rt변수를 통해서 증가, 감소 시켜주기 때문이다. 이때 가장 먼저 빨리 등장하여 더해주는 값이 두 값 사이의 최소 값이 될 것이다. 

이렇게까지만 생각하면 골드바흐는 쉬울수도?