[백준 / BOJ] 1153 네 개의 소수 (Java)

문제

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

1153번: 네 개의 소수

1 <= N <= 1,000,000 사이의 정수가 주어진다.

이때, 이 정수를 구할 수 있는 네 개의 소수를 구하는 문제다.

---

풀이

골드바흐의 추측을 알고있다면, 쉽게 풀리는 문제다.

궁금하면 여기로 보러가자. 골드바흐의 추측 : https://ko.wikipedia.org/wiki/골드바흐의_추측

골드바흐의 추측 - 위키백과, 우리 모두의 백과사전

골드바흐의 추측은 미해결 난제로

1) 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

2) 5보다 큰 모든 홀수는 세 소수의 합으로 나타낼 수 있다.

 

따라서, 우리는 증명이 아닌 추측을 할 수 있다.

 

"7보다 큰 모든 수는 4 소수의 합으로 나타낼 수 있지 않을까?" (8부터는 2+2+2+2로 가능하다.)

(반례를 찾거나, 증명을하면 필즈상을 받지 않을까)

 

이 논리를 따라서, 다음과 같이 알고리즘을 구현하면 하지만 정답이 나온다.

1. 입력을 받는다.

2. 입력이 8보다 작다면 -1을 출력한다.

3. 아니라면, 에라토스테네스의 채를 사용해 소수 목록을 만든다.

4. 소수 목록을 탐색하며, 정수를 만든다.

 

또한, 문제를 풀때 주의할점이, 시간초과를 피하기 위해선, 이분탐색으로 찾거나 나 처럼 그리디하게 큰 수부터 더해가며 만들어줘야 한다.

그리디하게 풀리는 이유는 다음과 같다.

"작은수의 소수는 큰 수 보다 더 밀집되어 있다. 따라서, 작은수를 이용해서 N을 만들수 있을 가능성이 더 높은데, 이는 현재 큰 수를 먼저 선택하더라도 손해보는것이 없음을 뜻한다."

 

 

주요 소스코드

    private boolean getPrimeComb(int remain, int cnt){
        if(cnt == 0 && remain != 0){
            return false;
        }
        if(remain == 0 && cnt == 0){
            return true;
        }
        boolean isEnd = false;
        int i = 0;
        for(; primeList.get(i) <= remain; i++);
        for(int j = i; j >= 0; j--){
            isEnd = getPrimeComb(remain - primeList.get(j), cnt-1);
            if(isEnd){
                System.out.print(primeList.get(j) + " ");
                break;
            }
        }
        return isEnd;
    }

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1153%20네%20개의%20소수/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃