[Dev-Ping9] 백준 9020번 - 골드바흐의 추측 (Java) (N을 2개의 수의 합으로 표현하기)

 

# 문제 설명

• 수학적 지식을 배워가는 좋은 문제다... (.. 😇)
• 수에 대한 센스가 있느냐가 코딩시간과 수행시간을 압도적으로 단축시킨다.
• 모든 경우의 수를 검색하여, 그중에 또 작은 경우를 찾는 바보가 저 말고 또 있으실까... ㅎ..ㅎ... (근데 통과는 됨..)

 

# 문제 풀이

• 입력으로 들어오는 N은 짝수이며, 어떠한 짝수를 두수의 합으로 나타내는 모든 경우의 수를 찾는 방법은 해당 짝수를 2로 나눈 뒤, 한쪽에는 + a 다른 한 쪽에는 -a를 취하는 방법이다.

 

[*기초..기초..] N = (N/2 - a) + (N/2 + a)

 

• 이 방법은 항상 만족하며, case를 빠트리는 경우도 없다.
• 즉, 해당 로직으로 가장 빨리 발견하는 두 소수의 조합이 최소의 차를 가지는 골드바흐 파티션이다.

 

 

 

# 구현 코드 1  :  N = (N/2 - a) + (N/2 + a)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

    static boolean isPrime(int num){
        if(num ==1 ) return false;
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        boolean[] primes = new boolean[10001];
        for(int i=2;i<=10000;i++){
            if(isPrime(i)){
                primes[i]=true;
            }
        }
        
        for(int i=0;i<T;i++){
            int n= Integer.parseInt(br.readLine());
            int large = n/2;
            int small = n/2;
            //짝수니까 n/2 + n/2 = n 이다.
            while(true){
                if(primes[large] && primes[small]) {
                    System.out.println(small+" "+large);
                    break;
                }
                large++;
                small--;
            }
        }
    }
}

 

# 구현코드 2 : 거의 dfs...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main{

    static boolean isPrime(int num){
        if(num ==1 ) return false;
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
    static int binarySearch(int[] arr, int start, int end, int target){
        int mid = (start+end)/2;
        
        if(start<=end){
            if(target==arr[mid]) return mid;
            else if(target>arr[mid]){
                binarySearch(arr, mid+1, end, target);
            }else{
                binarySearch(arr, start, mid-1, target);
            }
        }
        return -1;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int[] primes = new int[10001];
        int idx=0;
        for(int i=2;i<=10000;i++){
            if(isPrime(i)){
                primes[idx++]= i;
            }
        }


        for(int i=0;i<T;i++){
            int n= Integer.parseInt(br.readLine());
            int firstSmallIdx = (-1)*Arrays.binarySearch(primes,0,idx, n) -2;
            // System.out.println("#FSI: "+ firstSmallIdx);
            int mapIdx=0;
            Map<Integer,List<Integer>> map = new HashMap<>();
            for(int j=firstSmallIdx; j>=0;j--){// n^2....
                List<Integer> list = new ArrayList<>();
                for(int k=0;k<=j;k++){
                    if(primes[j]+primes[k]>n) break;
                    else if(primes[j]+primes[k]==n){
                        list.add(primes[j]);
                        list.add(primes[k]);
                        map.put(mapIdx++,list);
                    }
                }
            }
            

            if(map.size()==1) {
                System.out.println(map.get(0).get(1)+ " "+ map.get(0).get(0));
            }
            else{
                int min = 100_000;
                int[] ans = new int[2];
                for(List<Integer> item : map.values()){
                    int diff = Math.abs(item.get(0)-item.get(1));
                    if(min>diff) {
                        min = diff;
                        ans[0]=item.get(1);
                        ans[1]=item.get(0);
                    } 
                }
                Arrays.sort(ans);
                System.out.println(ans[0]+" "+ans[1]);
            }
        }
    }
}