[JAVA]1153 네 개의 소수

 📚 문제  

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

반례 확인 : https://testcase.ac/problems/1153

1153번 네 개의 소수 - Testcase AC

 

🔍 아이디어  

1. N미만의 소수를 모두 미리 찾는다.

2. 골드 바흐의 추측 짝수는 두개의 소수로 반드시 표현 가능하다. ( 즉, 짝수 + a + b 의 조합으로 만든다)

2-1. 짝수인 경우는 ( 2+2 + (짝수) 로 가능한지 확인) 

2-2 홀수 인 경우는 ( 2+3 +(짝수)로 가능한지 확인)

 

📝 풀이 

package 백준.수학.에라토스테네스의체;

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

public class Boj_1153_네개의소수 {
    private static List<Integer> primes = new ArrayList<>();
    private static boolean[] isPrime;

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

        int N = Integer.parseInt(br.readLine());
        if (N < 8) {
            System.out.println("-1");
            return;
        }

        findPrimes(N);
        List<Integer> path = new ArrayList<>();
//      골드바흐의 추측 ( 짝수는 항상 두 소수의 합으로 표현이 가능하다 => 짝수가 되면 찾을수 있음)
        if (N % 2 == 0) {
            path.add(2);
            path.add(2);
            N -= 4;
        } else {
            path.add(2);
            path.add(3);
            N -= 5;
        }
        for (int prime : primes) {
            int other = N - prime;
            if (other >= 2 && isPrime[other]) {
                path.add(prime);
                path.add(other);
                break;
            }
        }

        for (int num : path) {
            System.out.print(num + " ");
        }
    }

    private static void findPrimes(int n) {
        isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
    }
}

 

 

더 빠른 코드 ( 쓸모없이 이진 탐색 넣기..)

package 백준.수학.에라토스테네스의체;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Boj_1153_수정완료 {
    private static List<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        findPrimes(N);

        if (N % 2 == 0) {
            //짝수
            if (findDfs(N - 4, 2, new ArrayList<>(List.of(2, 2)))) {
                return;
            }
        } else if (N != 1) {
            //홀수 (하나는 짝수여야 한다 - 2가 포함)
            if (findDfs(N - 5, 2, new ArrayList<>(List.of(2, 3)))) {
                return;
            }
        }

        System.out.println("-1");
    }

    private static boolean findDfs(int n, int depth, List<Integer> path) {
        if (path.size() > 4)
            return false;

        if (depth == 0) {
            if (path.size() == 4 && n == 0) {
                for (Integer number : path) {
                    System.out.print(number + " ");
                }
                return true;
            }
            return false;
        }

        for (int i = upperBound(n); 0 <= i; i--) {
            path.add(primes.get(i));
            //찾음
            if (findDfs(n - primes.get(i), depth - 1, path)) {
                return true;
            }
            path.remove(path.size() - 1);
        }
        return false;
    }

    private static int upperBound(int n) {
        int start = 0;
        int end = primes.size() - 1;
        int upperBound = 0;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (primes.get(mid) <= n) {
                start = mid + 1;
                upperBound = mid;
            } else {
                end = mid - 1;
            }
        }
        return upperBound;
    }

    private static void findPrimes(int n) {
        boolean[] isNotPrime = new boolean[n + 1];
        isNotPrime[0] = isNotPrime[1] = true;
        for (int i = 1; i <= n; i++) {
            if (!isNotPrime[i]) {
                primes.add(i);
                for (int j = i; j <= n; j += i) {
                    isNotPrime[j] = true;
                }
            }
        }
    }
}